« first day (3796 days earlier)      last day (1135 days later) » 

12:00 AM
The whole alien thing was fun when I was in my teens but now I feel like if they landed on the Whitehouse lawn I would say "oh yeah, cool", and carry on with my day.
 
Would be fun if aliens come to earth, say hello, give us nothing and leave
 
If I was an alien I'd visit the donut-shaped planet first too
 
So I got this design question, have you guys ever had the case where a you can swap the data but you can't really provide a valid move operator?
 
 
8 hours later…
8:30 AM
@Mikhail I had problems very close from that at some point yeah
 
8:44 AM
So I ran into this issue where I have this vector<objects> but the objects have members that refer to indexes in the vector. The vector<objects> is that object pool that I've been struggling to get right. The objects need to manipulate other items in the vector as part of their destruction or construction. When when vector.resize() is called it isn't clear if they refer to the original or resized vector. Among other issues.
 
can you get away with not relocating object inside the vector?
 
You mean, not resizing the vector?
 
Not really sure how that would work. One alternative to facilitate resizing the vector<object> pool is to copy everything into a new vector<object> and then somehow std::move() the copy into the old place. But I'm not sure if this will fix anything.
Fuck, explaining why its taking so long to get this right will be challenging, especially since I find myself, once again, the only person who is doing C++ (or really any language that requires memory management).
 
my thought was leaving the old object in place with a freelist on the side
no need to rejigger the vector then unless there is a massive update you need to do anyway
 
8:58 AM
I mean, I have an std::vector<shared_ptr_data_blocks> and a free list. I'm trying to write, among other things, a object pool backed version of std::shared_ptr to avoid malloc overhead for small allocations.
But ultimately, I'll need to reallocate the objects on my pool. It's just that while a re- allocation is happening the objects may need to refer to things on the pool.
 
when need to expand your pool you could instead allocate a fesh new chunk and keep the old one as well
so instead of a vector you have std::list<std::array<shared_ptr_data_blocks, 512>>
 
Thats certainly an interesting thought.
Okay well time to go to sleep, au revoir
 
deja vu with a recent discord discussion...
and for completeness the snippet for easy freelist creation with arbitrary objects: coliru.stacked-crooked.com/a/7e8203a1d557413e
 
that looks like a variant...
 
but it lets you store a pointer to its own type for freelist purposes
without needing to add that inside the object
 
9:12 AM
doesn't the variant have the type information?
you mean the pointer to the list where the variants live?
 
the freelist pointer when you implement it as a linked list
 
Sometimes I think its memory inefficient to store all the variants in one list due to the added cost of having the variant type member.
I actually avoided variants to avoid paying the 8 byte per object variant tax.
 
if you don't mind doing the raii minutia yourself you can keep 512 worth of bits on the side for that
 
Hmm, the idea of never reallocating the objects does sound like an interesting one. I'll give it a whirl tomorrow. Thanks for the suggestion.
 
10:01 AM
@ratchetfreak isn't that like rebuilding std::deque manually?
 
maybe, but here Mikhail wants to avoid small allocations and have pointer stability, in this way he isn't bound to the implementation of std::deque to achieve that
 
It's kind of sad that we end up reimplementing our own standard containers
 
it'd be nice if there was a std::object_pool
or std::object_pool_allocator with these guarantees
 
10:26 AM
It is really weird, how the standard library containers are both too generic and too specialized at the same time.
 
It would be easier to create an allocator for list nodes if a list node was an accessible type
But that still wouldn't solve everything
I reimplemented my own std::list equivalent recently, and add functions as I need them in my library
So two days ago I reimplemented std::list::splice and std::list::merge
Then once everything worked I checked the standard library implementations
And it turns out that the one in libstdc++ isn't really optimized
When merging it seems that it splices nodes one by one instead of splicing however many fit at the same time
Which means a whole lot of useless node relinking
 
std::list converts the passed allocator into a list_node allocator doesn't it,
 
I suppose so
 
it makes it possible but still rather awkward
 
To give you an idea of the shortcomings of std::list
 
10:41 AM
wrong title?
 
The algorithm above shows different versions of the melsort algorithm which uses doubly linked lists internally
The only difference between these versions is the quality of impementation of the list used and its allocator
 
Melsort 2018: `std::list` with `std::allocator`
Melsort 2021.0: `std::list` with libstdc++ `bitmap_allocator`
Melsort 2021.1: custom list implementation based one a fixed-size node pool
The others are my custom list implementation with a gradually better list::merge algorithm
The takeaway is that bitmap_allocator, when available, is pretty much always better than std::allocator for std::list
But at the end of the day, when it really matters you're better off writing your own list
 
11:03 AM
And I just realized that I have other optimizations to try :o
And it's pretty much only possible because I have my own list implementation
 
 
9 hours later…
8:30 PM
@ratchetfreak So related to this approach, have you ever thought about how to scale it really large allocations? Have an optimal solution for allocating hundreds of gigs as well as a few kilobytes, maybe have the size of the chunk scale? Or maybe just always allocate like 10 megabytes (I think memory pages are usually fixed..).
 
 
3 hours later…
11:21 PM
well this is awkward.
 

« first day (3796 days earlier)      last day (1135 days later) »