search

attic-labs / noms

The versioned, forkable, syncable database
Apache License 2.0
7.45k stars 267 forks source link

`Collection.Len()` should be cheap #3759

Closed ghost closed 6 years ago

ghost commented 6 years ago

It's very likely that API users will assume it is. E.g. for i := 0; i < l.Len(); i++.

Right now it does some decoding for each call.

kalman commented 6 years ago

A while ago, New{List,Set,Map}() would pre-compute the length and store it on the struct directly.

arv commented 6 years ago

We currently sum up the numLeaves of all elements of a sequence. This was the case even before the current changes. This requires us to do a bunch of varint decoding but that is it. We already know the index of where this varint is located so we do not have to seek through the sequence at least.