Hacker News Reader

Comment by kabdib | Hacker News Reader

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.

View on HN

The VList paper - which I archived at http://trout.me.uk/lisp/vlist.pdf to avoid having to google the bloody thing every time - is an interesting hybrid.

Thank 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.

trout.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.

Thanks for referring to the article. Great read!

http://trout.me.uk/lisp/ and 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.

Regarding 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

Thank you!

Added to my /lisp/ directory for when I inevitably realise I've forgotten where I saw it :D

Ironically, 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.

OSes do already provide this ability: mmap.

Maybe 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.

Or, you can map new space onto the end of an existing mapping, at a slightly greater cost of keeping track. Mremap is usually better.

If 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.

/dev/hugepages/ is a good place to put this if you have enough control over the host.

That sounds like a lot of work unless you absolutely have to have a contiguous allocation of every element.

If you don't need that, you can get "O(1.1)" access and nice heap behavior with an indirection or two, and the implementation is likely to be lots more portable and standards-friendly than if you also dragged in a bunch of OS mmap() semantics (which tend to have exciting, platform-dependent misfeatures).

Also, I would have to reach for the mmap() man page. I have malloc() right in front of me. :-)

Right, the ability to relocate a chunk of memory to a new virtual address (with more capacity at the end) without doing a physical copy would be an interesting way to solve the problem.

I don't know if anyone has done research on integrating data structures and OS functionality in this way. Interesting idea.

We needed to get things running again rather quickly, though :-)

Some game engine developers have certainly used this idea, to prevent any reallocations when the dynamic array needs to be resized. Such as:

https://ruby0x1.github.io/machinery_blog_archive/post/virtua...

Some ECS implementations use this to reduce the overhead of dynamic arrays, as well as ensuring pointer stability of the items stored. For example entt:

https://skypjack.github.io/2021-06-12-ecs-baf-part-11/

And here's a library implementing a resizable, pointer-stable vector using virtual memory functionality from the OS:

https://github.com/mknejp/vmcontainer

End of page allocation has been a real life-saver. I have it rigged up to the core allocators of the game engine I work with, so you can switch it with a cmdline switch; if you suspect an overwrite, you switch on the EOP allocator ( using more memory temporarily ), and bang, you get a segfault where you went off the end / used-after-free.

Linux has mremap() for this. macOS has vm_remap(). Not sure about other operating systems.

You can certainly allocate memory at controlled addresses using mmap or VirtualAlloc.

But you should not play virtual memory games at runtime in an application that you expect to be scalable. Unmapping memory or changing its permissions requires propagating the change to all threads in the process. On x86, the performance impact is dramatic. On ARM64, it’s not as bad but it’s still there.

Also, even 64 bits can go fast when you start using high bits, separate pools for different purposes, etc.

I somehow misread your comment the first time through and thought you were suggesting the ability to ask the OS: "Hey, I'm a pointer, is there anything in front of my block of memory, if so can you move it elsewhere so that I can expand?" This would of course be a pretty silly idea but it would be funny to give the OS folks a whole new class of use-after bugs to worry about.

Edit: Let's call it "memoveouttamyway"

Isn't that `realloc`? At the allocator level rather than OS level, but still.

glibc realloc(3) does this on Linux, by way of mremap(2) with MREMAP_MAYMOVE [1]. (Just confirmed on my local machine using strace(1).)

Unfortunately, libstdc++ does not (to my knowledge) use realloc(3) or mremap(2) for vector resize, nor could it in many situations due to the semantics of C++.

[1] https://github.com/bminor/glibc/blob/15a94e6668a6d7c5697e805...

If 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.

And 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.

You 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

If you have to do a binary search in a million elements you'll have cache misses anyways

Sure, ln cache misses. With a linear search through pointers you have n cache misses.

Correct 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

Another name for that is "B* tree". Or anyway a thing with similar performance characteristics.

Right, 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).

simple 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?

That'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.

Ah thanks, I didn't read closely enough the first time.

For a simple and readable implementation of a Python btree see this:

https://github.com/samsquire/btree

I tried to keep the implementation as simple as I could.

also what a deque (C++) does

True... except in MSVC. std::deque in MSVC is cursed.

Targeting MSVC, use boost::deque or something, instead. Boost containers are generally fairly good, although they are more or less unmaintained nowadays. (E.g., boost::unordered_map::reserve doesn't work.) Or, like many of us, ignore performance on MS targets because anybody who cares about performances is running something else.

Why?

https://github.com/AcademySoftwareFoundation/openvdb/issues/...

Longer answer is that the size of the "blocks" is limited to 512 bytes or one element, whichever is larger. So unless your elements are really tiny, it is strictly a pessimization.

Many of the STL containers in MSVC are incredibly cursed. Even std::vector is implemented in such a weird way, that you can't debug it easily with any debugger other than Visual Studio. And it's incredibly slow on Debug mode, up to the point that it's unusable... (Because of these reasons I just switched to using my own Vector<T> class recently)

I think there's a very good reason why old gamedevs who were stuck with developing on Windows largely ignored the STL and made their own containers / utility functions: MSVC's STL was just awful.

I always wondered why we weren’t allowed to use the STL in the Windows division in the 00’s. This probably explains it.

There was a lot of BS, as well. It is impossible to tease out which was what.

> Many of the STL containers in MSVC are incredibly cursed. Even std::vector is implemented in such a weird way, that you can't debug it easily with any debugger other than Visual Studio. And it's incredibly slow on Debug mode, up to the point that it's unusable... (Because of these reasons I just switched to using my own Vector<T> class recently)

Here's a link to an old HN discussion that offers some insight on the performance of MSVC's STL in debug.

https://news.ycombinator.com/item?id=18939260

The "cursed" keyword hand-waves over the problem and suggests it originates in the acritical propagation of ignorant beliefs. Sometimes clarifying these is just a Google search away.

Yes, I know that already. And good luck with dealing all the linker/ABI issues from changing that setting.

> ignore performance on MS targets because anybody who cares about performances is running something else.

That's a strange take. Surely games still represent a significant chunk of the demand for C++ developers that need to care about performance?

Thus, "many". Game coders would not be among those.

My 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…

This sounds like you need a log structured merge tree.

Reply on news.ycombinator.com