but struggle when a lot of inserts and updates need to happen.
I ran across this with Redis recently. Redis has an internal data structure called ziplist that's a doubly linked list with no pointers. It just uses byte offsets to the next element, so all elements are in one contiguous block of memory. It's great because you can store a lot of values compactly without needing 1 to 5 pointers (8 to 40 bytes) overhead per element in your data structure.
But, a problem shows up when you want to insert or delete items. Every insert or delete requires expanding or shrinking the entire solid-chunk-of-memory allocation, which isn't the fastest thing in the world when your allocation is large. Also, inserting into the HEAD requires copying the _entire_ ziplist up exactly one element position because the block of your memory layout just changed.
So, obviously these things are useful, but their usefulness degrades as your solid blocks of memory hit cache limits. Everything is super fast when your entire ziplist fits in L1, still about the same in L2, worse in L3, and horrible if your ziplist grows any larger.
But, what can we do? We can fix the entire problem by creating a traditional linked lists of solid memory block ziplists. Now, each ziplist can remain small (8 KB to 16 KB), and when we grow bigger, we just cut a new ziplist, pointer-attach it to the previous ziplist, and now we have a minimal-pointer, high-locality data structure with unlimited growth potential without performance defects. It doesn't buckle under inserting or updating arbitrary elements since each memory block is isolated to a maximum ~8 KB size (reminder: your L1 cache is 32 KB to 64 KB depending on architecture) and now your memory usage due to pointer overhead is now also _greatly_ reduced (assuming your data was small and dominated or matched by pointer overhead size in the first place).
As a double bonus, now when your data structure is a solid block of memory, you can compress individual contiguous memory blocks (usually with great compression ratios) because your contents will tend to be homogeneous in shape inside the same container. Result: huge reduction in pointer overhead + sequential access + compression = best of all possible worlds.
This isn't news. Arrays are fast until you need to insert/delete in them, then they get horrible. This is why we have B-trees. Every page in a B-tree is essentially a sorted array - you can find items in it quickly using binary search, and you can insert/delete in it relatively quickly because it has a small bounded size. When you need to grow beyond a single page you do a page-split and add a parent above it, etc. B-trees are the optimal implementation of dynamic arrays, end of story.
This reply is golden. It starts off completely dismissive with "this isn't news" and it ends completely dismissive with "end of story." I am quite sorry my free internet post failed to meet your quality guidelines.
A wise man once said: Things have now gotten to the stage where I flinch slightly as I click on the "comments" link, bracing myself for the dismissive comment I know will be waiting for me at the top of the page.
1. Name array strongly implies that it has an underlying continuous memory location associated with it. All of modern scripting languages have some form of dictionary, map, set, or hashtable which is implemented using insert/update friendly approach.
1a. Typical workload for array is to iterate over it doing something with each element, B-Tree is strictly worse in iterating over all elements compared to static array.
2. Most instantiated dynamic arrays rarely perform deletes. Most common operation that could change size of array is push_back, and amortized cost for inserts is probably way less than chasing pointers in B-Tree.
3. B-Trees were created and optimized for HDD performance. With current SSD and memory trends, there are simply better data structures to use.
4. Pointer chasing got a lot more expensive relative to continuous memory scanning. This is mostly due to majority of memory performance increases coming from increased throughput as opposed to lower latency.
This does not mean B-Trees are bad, in fact they are still heavily utilized in databases because they scale extraordinarily well with data size. They are commonly used for indexes because membership testing (single value lookup) and range lookups are O(1), and updates/deletes are generally very fast as well.
B-trees are “optimal” in the sense that they’re O(log N) for all the usual operations (insertion/deletion, appenditem, getitem, setitem, and even concatenation with some work) but simple exponentially-growing arrays are O(1) for getitem, setitem, and appenditem, which is asymptotically faster. Also, their constant factors are better, and their memory footprint is smaller.
hyc_symas’s comment seems a little confused because they are talking about doing binary search within B-tree pages. But if you’re using B-trees to implement dynamic non-sparse arrays, which seems to be the topic, you don’t need any binary searches. You can just subtract the beginning-of-page index from the index you’re indexing to in order to get the offset within the page.
That kind of comment, managing to be simultaneously ignorant and arrogantly dismissive, is why I don’t comment much on HN these days.
Sorry, but the only ignorance here is your own. You assumed that "storing into an array" means that the array index is the only thing relevant for locating a record. But the fact that you're talking about inserts/deletes means that the array index of a particular element is mutable and therefore insufficient for uniquely locating a record. Which means you must perform some type of search to retrieve a particular item. Your O(1) getitem is nonsense.
Yes, you can say "give me the 5th element of this array" but the discussion was about maps/dictionaries, where you're more often going to say "give me item foo that was inserted before".
When folks like you post while obviously not paying attention, yes, you elicit a dismissive response.
I would be unsurprised if it was for legacy reasons. Both of those programming languages were written over twenty years ago. Furthermore, arrays play nicely with C extensions.
So if you have fixed sized 'ziplists', why don't you do a memmove() instead of a realloc() on inserts, then split your array on overflow? That would be 1 malloc per 1024 inserts assuming 8 byte data in an 8K page instead of 1 malloc per insert.
This would be vastly more cache friendly, and you would be fragmenting your heap dramatically slower. You could even mmap() a scheme like this, but that's another story!
why don't you do a memmove() instead of a realloc() on inserts
Oh, it's actually worse than that because when inserting we do a realloc (which could require automatically copying the entire memory block), then (if inserting to the head) we memmove the entire contents down to the end of the new allocation. Fun!
Mainly we don't pre-allocate because it's built on top of existing components, and the existing components don't do that. The actual "max size" limit is configurable and we don't really want to allocate the full max size for each list up front. If you have 500,000 lists each with 3 40 byte elements (~60 MB total), it would be overkill to allocate 500,000 8 KB blocks (~4 GB total).
Ideally, we would automatically determine if the user is doing "big operations" then switch to a page-based approach versus smaller "store as much data as compactly as possible" approaches, but it's just not done yet.
I ran across this with Redis recently. Redis has an internal data structure called ziplist that's a doubly linked list with no pointers. It just uses byte offsets to the next element, so all elements are in one contiguous block of memory. It's great because you can store a lot of values compactly without needing 1 to 5 pointers (8 to 40 bytes) overhead per element in your data structure.
But, a problem shows up when you want to insert or delete items. Every insert or delete requires expanding or shrinking the entire solid-chunk-of-memory allocation, which isn't the fastest thing in the world when your allocation is large. Also, inserting into the HEAD requires copying the _entire_ ziplist up exactly one element position because the block of your memory layout just changed.
So, obviously these things are useful, but their usefulness degrades as your solid blocks of memory hit cache limits. Everything is super fast when your entire ziplist fits in L1, still about the same in L2, worse in L3, and horrible if your ziplist grows any larger.
But, what can we do? We can fix the entire problem by creating a traditional linked lists of solid memory block ziplists. Now, each ziplist can remain small (8 KB to 16 KB), and when we grow bigger, we just cut a new ziplist, pointer-attach it to the previous ziplist, and now we have a minimal-pointer, high-locality data structure with unlimited growth potential without performance defects. It doesn't buckle under inserting or updating arbitrary elements since each memory block is isolated to a maximum ~8 KB size (reminder: your L1 cache is 32 KB to 64 KB depending on architecture) and now your memory usage due to pointer overhead is now also _greatly_ reduced (assuming your data was small and dominated or matched by pointer overhead size in the first place).
As a double bonus, now when your data structure is a solid block of memory, you can compress individual contiguous memory blocks (usually with great compression ratios) because your contents will tend to be homogeneous in shape inside the same container. Result: huge reduction in pointer overhead + sequential access + compression = best of all possible worlds.
Other details/comparisons at https://matt.sh/redis-quicklist-visions