3 ms·
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 mallo
by t1m 12y ago
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!
- seiji 12y agowhy 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.