News for hackers. Stuff that matters.
Re:Drop millions of allocations by using a linked list (2015) by matheusmoreira on Friday March 12, 2021 @07:42AM (#26435170)
Why can't we have this as a general interface in standard libraries? For example, we could have a contextual allocation function:

  // Contiguous array of 1024 objects of type
  context = contextual_allocation(1024, sizeof type);

  // obtain pointer to next free object 
  object = allocate(context);
Re:Drop millions of allocations by using a linked list (2015) by alexhutcheson on Friday March 12, 2021 @09:47AM (#26436333)
This is called arena allocation, and there are many implementations of the concept.

For example, the C++ Protocol Buffers library has an Arena class, which is documented here: https://developers.google.com/protocol-buffers/docs/referenc...

The EA STL has fixed_allocator, which implements a similar concept while exposing more low-level details in the API: https://github.com/electronicarts/EASTL/blob/master/include/...

Re:Drop millions of allocations by using a linked list (2015) by sgtnoodle on Friday March 12, 2021 @12:35PM (#26438358)
I'd describe it more as a pool or block allocator.

An arena allocator is specifically optimized for incremental allocation and then bulk deallocation (the entire arena is freed at once).

The example code instead appears to create a context of a number of fixed sized blocks. Because of the fixed size, the allocator can make a lot of simplifying assumptions and generally achieve constant time algorithmic complexity, while allowing for individual allocations to be freed and reused.

Re:Drop millions of allocations by using a linked list (2015) by vbarrielle on Friday March 12, 2021 @07:50AM (#26435252)
Zig requires the allocator to be specified for each allocation: https://ziglang.org/documentation/0.5.0/#Memory

This has a huge impact on the API design, so I don't think this can be retrofit in standard libraries of existing languages (because of backwards compatibility).

Re:Drop millions of allocations by using a linked list (2015) by thechao on Friday March 12, 2021 @09:17AM (#26436038)
In the mid 00s, my advisor had me explore the concept of adding default parameters to C++ functions where the default snagged the nearest lexically scoped named object of the right type from the calling environment, i.e.,

    int someFunctionThatAllocates(int A, int B, allocator const& alloc = default);
Then in the calling environments:

    {
        auto& alloc = james;
        if (someFunctionThatAllocates(4, 5)) // ok, uses 'alloc'
        {
        }
    }
    {
        if (someFunctionThatAllocates(4, 5, james)) // ok, uses 'james'
        {
        }
    }
    {
        auto& alloc1 = james;
        if (someFunctionThatAllocates(4, 5)) // error: no `alloc` in scope
        {
        }
    }
It handily solves a number of problems. In particular, we were looking at how we manage heap allocation for large sparse matrix libraries a la MTL4.
Re:Drop millions of allocations by using a linked list (2015) by gpderetta on Friday March 12, 2021 @10:12AM (#26436629)
Interesting. Isn't this this vaguely reminiscent of implicits in Scala?
Re:Drop millions of allocations by using a linked list (2015) by thechao on Friday March 12, 2021 @06:04PM (#26442033)
Yep; Martin suggested it to us; he said the ergonomics were good.
Re:Drop millions of allocations by using a linked list (2015) by injidup on Friday March 12, 2021 @12:59PM (#26438681)
It's called implicits in Scala
Re:Drop millions of allocations by using a linked list (2015) by kristoff_it on Friday March 12, 2021 @08:06AM (#26435406)
For an overview of how Zig does this and at the same time a nice overview on different types of allocators:

What's a Memory Allocator Anyway? by Benjamin Feng

https://www.youtube.com/watch?v=vHWiDx_l4V0

Re:Drop millions of allocations by using a linked list (2015) by fanf2 on Friday March 12, 2021 @09:42AM (#26436297)
Re:Drop millions of allocations by using a linked list (2015) by latch on Friday March 12, 2021 @07:48AM (#26435226)
I believe this is how Zig works. Specifically the FixedBufferAllocator. It can further be paired with the ArenaAllocator to make management dead simple.