13 ms·
The first week into my prior job, I had to fix an in-production bug involving quadratic vector growth that was tipping over servers. The vector implementation g
by kabdib 4y ago
The first week into my prior job, I had to fix an in-production bug involving quadratic vector growth that was tipping over servers. The vector implementation guaranteed too much, namely consecutive memory layout (which wasn't needed, and if we had needed it, it would have been a mistake).
Decomposing that vector into recursive subvectors solved the problem. Going from a few tens of millions of elements in a single contiguous vector (with consequent -- and bad -- heap fragmentation!) to nested vectors with a few thousand elements each brought us back online again.
Which is to say: Vectors are nice. Lists are nice. Use appropriate data structures for your scale, watch your semantic dependencies, and don't get hung up on dogma.
- mst 4y agoThe VList paper - which I archived at http://trout.me.uk/lisp/vlist.pdf http://trout.me.uk/lisp/vlist.pdf to avoid having to google the bloody thing every time - is an interesting hybrid.
- GeorgeWBasic 4y agoThank you for that. That's a concept I remembered reading about, but I couldn't remember the name and had no way to find it again.
- mst 4y agotrout.me.uk/lisp/ and trout.me.uk/gc/ are both basically archives of "stuff I knew I'd suffer that problem with" and it's a pleasure every time the contents come in handy for people who aren't me. Also back when I was still pretending to be a mathematician I used both GWBASIC and UBASIC for assorted purposes so thank -you- for the nostalgia kick.
- simplotek 4y agoThanks for referring to the article. Great read!
- mst 4y agohttp://trout.me.uk/lisp/ http://trout.me.uk/lisp/ and http://trout.me.uk/gc/ http://trout.me.uk/gc/ are both "selected stuff I knew I'd have trouble finding again later" and I wish you great joy of them. Still sad that John Shutt (creator of 'kernel lisp') passed away while I was still procrastinating dropping him an email - I think the only other 'thank you' I've most regretted not sending in time was to Terry Pratchett.
- sparkie 4y agoRegarding section 4.1 and 8 in this paper, it uses several software implementations of MSB and gives a performance comparison between the VList and RAOTS from which it was derived. It doesn't utilize hardware instructions which can improve the MSB calculation and eliminate branches (eg, clz/lzcnt or bsr). It's worth having another look at RAOTS using an optimized MSB which will leverage instructions available in modern hardware, and see how its performance compares to the VList. https://cs.uwaterloo.ca/~imunro/cs840/ResizableArrays.pdf https://cs.uwaterloo.ca/~imunro/cs840/ResizableArrays.pdf
- mst 4y agoThank you! Added to my /lisp/ directory for when I inevitably realise I've forgotten where I saw it :D
- diabeetusman 4y agoCorrect me if I'm wrong, but it sounds like you're describing an Unrolled Linked List [1]? If so, neat! [1]: https://en.wikipedia.org/wiki/Unrolled_linked_list https://en.wikipedia.org/wiki/Unrolled_linked_list
- pencilguin 4y agoAnother name for that is "B* tree". Or anyway a thing with similar performance characteristics.
- kabdib 4y agoRight, though we didn't need full tree semantics (just fast random access and an append that didn't spool up the fans on the servers). I would hate to have to do a full balanced b-tree on short notice. (We also had rather terrible extra requirements that made using an off-the-shelf thing from, say, the STL work in our environment).
- dilap 4y agosimple vector implementations will do a full realloc and recopy when you run out of space. so O(1) amortized but O(N) every so often. another implementation strategy, at the cost of using some extra memory, is to allocate the new space, but only copy over a bit at a time, each time a new element is added -- so every add is still O(1). no long pauses. (well, assuming the memory alloc is still fast. which i think it should be in practice? tho i'm not super familiar w/ that stuff.) just curious, do you think that solution would have worked for your situation too?
- kabdib 4y agoThat's exactly the strategy that was tipping over. Once you start resizing vectors of tens of megabytes, it's kind of over. You can start playing games by accelerating capacity allocation when a vector rapidly starts growing extremely large. This doesn't solve the problem that vectors sometimes guarantee too much for what you need.
- dilap 4y agoAh thanks, I didn't read closely enough the first time.
- samsquire 4y agoFor a simple and readable implementation of a Python btree see this: https://github.com/samsquire/btree https://github.com/samsquire/btree I tried to keep the implementation as simple as I could.
- bluGill 4y agoIf your elements are in the millions than a tree might be better, depending on what you do. If you traverse the whole thing often then vector is best, but at a million a tree will do a search for element faster despite the cache misses. I don't know where the line is, but in general you are probably not close to that line so default go vector. However as your point is, sometimes you are over that line.
- sally_glance 4y agoAnd if you really need it you can even do both tree and vector simultaneously - just make sure both consist of pointers only so you avoid update/sync issues.
- bluGill 4y agoYou can, but probably shouldn't. The pointers means a cache miss when you follow it. Putting everything in the vector is the point, otherwise the map is potentially faster
- ndriscoll 4y agoIronically, if you weren't using huge pages, the operating system was already doing this for you anyway, and your contiguous segments weren't contiguous. This does suggest functionality that the OS should provide: let the program remap memory somewhere else in its address space to obtain a larger contiguous chunk of addresses without copying data. This wouldn't help much if you have direct pointers, but I think e.g. Java has a layer of indirection that would let it benefit from remapping to grow ArrayLists. I don't know if things already work this way. It should make speculative fetches easier for the processor since now it understands what you're doing via the memory map. Edit: taking this idea a little further is actually fascinating: use the type system to separate objects into pools based on type, and instead of pointers, use indexes into your pool. You can move the pool for free to grow/shrink it. I think you could even do this with pointers and full hardware acceleration today if you used the high bits to tag pointers with their types and used remapping at the hypervisor level to move the pools (so the address in the application level doesn't change). You could do some crazy stuff if the application could coordinate multiple levels of virtual memory.
- pencilguin 4y agoOSes do already provide this ability: mmap.
- ndriscoll 4y agoMaybe I'm just not seeing it, but I don't see how mmap let's you remap an existing address to a new one? Looks like there is a mremap on Linux in any case.
- pencilguin 4y agoOr, you can map new space onto the end of an existing mapping, at a slightly greater cost of keeping track. Mremap is usually better.
- comex 4y agoIf you want to stick to mmap, you can do it by creating a file which doesn’t have any actual disk backing (one way to do this is with POSIX shm_open), and handling all memory allocations by mmapping parts of that file rather than mapping true anonymous memory. Then, ‘remapping’ an address to a new one is a matter of calling mmap again with the same file offset. Unlike mremap, this allows mapping the same memory at different addresses simultaneously, which can be useful for some purposes.
- AtlasBarfed 4y agoThis sounds like you need a log structured merge tree.
- taf2 4y agoMy Forman always would tell me KISS - (keep it simple stupid), maybe there is another single word for just solve the problem at hand silly - j,s,p,a,h,s - doesn’t really roll off the tongue the same way…