4 ms·

talloc is based on my library called halloc [1], which stands for hierarchical allocator. The idea is that every malloc'ed block can be assigned a parent block.

talloc is based on my library called halloc [1], which stands for hierarchical allocator. The idea is that every malloc'ed block can be assigned a parent block. Freeing the parent block also frees all its children in a recursive fashion, and that's about it. I cooked up halloc several years ago when implementing IKE (the IPsec keying protocol) library and it proved to be very useful for reducing the verbosity of the code without loosing any clarity. Tridge fluffed up halloc to make the API more fit and convenient for Samba code, and talloc came out. I still like my version better though because it is simpler and (subjectively) more elegant. [1] http://swapped.cc/halloc http://swapped.cc/halloc

FooBarWidget 16y ago
No offense intended, but I have to say I was a little bit disappointed by halloc. I expected it to use a custom allocation scheme, like malloc()ing large chunks of memory in one go in order to reduce malloc() time and space overhead and to increase locality of reference. Instead it looks like it just malloc()s every object separately. I'm sure some people will find halloc useful, but in my C++ project where I already use smart pointers I didn't see any advantage in using halloc. It doesn't look like talloc is any better.
- rwmj 16y ago
  Do you have evidence that rolling your own suballocator under malloc is better than just using malloc. By "evidence" I mean you actually measured it, not arm-waving.
  - FooBarWidget 16y ago
    Yes. For example my app has a hash table which it fills upon every request. After this initial filling, not more hash table entries are set. At the end of the request the hash table is deleted, and a new one is created at the next request. I improved performance a bit by clearing the hash table instead of deleting and recreating it. What gave me an even bigger boost in performance was by using a custom allocator that allocates big chunks of memory in a single operation. The thing is my app is already not doing a lot of work per request so almost any speedup is noticeable.
    - scott_s 16y ago
      You saw benefit because you implemented a custom allocator whose behavior was optimized to the memory access pattern that you planned to use with it. Any decent implementation of malloc already allocates large chunks of contiguous memory from the operating system and tries to maintain locality among allocations. It's also possible that you saw performance improvement from the removal of a function call - it's possible that the call to your custom allocator could be inlined, whereas malloc has to be a function call. My understanding of halloc and talloc is that they are general purpose allocators. A pure library approach - that is, without source code analysis and code generation - won't be able to tailor the allocation scheme based on the data structures themselves.
      - latitude 16y ago
        FooBarWidget got a good point though. When two blocks are explictly tied into a parent-child relationship, it gives the allocator valuable locality information. It is another matter that halloc separates allocation and block binding steps, so the relationship information is not available at the allocation time, and so it cannot utilize these locality hints.
- lobster_johnson 16y ago
  I suspect the idea behind the library is not performance optimization, but convenience. It's sometimes much more convenient to let someone track allocation dependencies than doing it yourself.
- latitude 16y ago
  You appear to be mixing two things here. What you described is a form of a "slab allocator" whereby all blocks in a certain size range are allocated from one big piece of memory that is sliced into equally sized chunks. This is really fast, it works great for smaller blocks and it is the way to speed up the STL-heavy code. I did some profiling a while back and a lock-free slab allocator delivered 10x speed up in the code that operated with std::map and strings. The second thing is locality. An allocator like halloc could theoretically utilize the fact that two blocks are explictly marked as related and allocate them close to each other. However, for this to work the allocation function needs to be passed a pointer to the parent block, which is not the case with halloc. So the API needs to change, the implementation needs to change too, and then it will no longer be a light implementation of a simple idea, but something else.
alexgartrell 16y ago
Thank you! Halloc works great for Mongrel2 http://mongrel2.org/dir?ci=4ff647658e12c6f4&name=src/mem http://mongrel2.org/dir?ci=4ff647658e12c6f4&name=src/mem edited to add (for third parties): iirc, halloc is mainly used by mongrel2 in things like the routes table, where it makes the code for maintaining the trie much cleaner.
lobster_johnson 16y ago
So it's like NSZone in Objective-C. In Obj-C you can associate any allocated object instance with a zone (unless you want to use the default, runtime-provided zone); deallocating a zone will also deallocate all the instances. Useful for things like trees where you can deallocate every node just by deallocating the root.

FooBarWidget 16y ago

No offense intended, but I have to say I was a little bit disappointed by halloc. I expected it to use a custom allocation scheme, like malloc()ing large chunks of memory in one go in order to reduce malloc() time and space overhead and to increase locality of reference. Instead it looks like it just malloc()s every object separately. I'm sure some people will find halloc useful, but in my C++ project where I already use smart pointers I didn't see any advantage in using halloc. It doesn't look like talloc is any better.

rwmj 16y ago
Do you have evidence that rolling your own suballocator under malloc is better than just using malloc. By "evidence" I mean you actually measured it, not arm-waving.
- FooBarWidget 16y ago
  Yes. For example my app has a hash table which it fills upon every request. After this initial filling, not more hash table entries are set. At the end of the request the hash table is deleted, and a new one is created at the next request. I improved performance a bit by clearing the hash table instead of deleting and recreating it. What gave me an even bigger boost in performance was by using a custom allocator that allocates big chunks of memory in a single operation. The thing is my app is already not doing a lot of work per request so almost any speedup is noticeable.
  - scott_s 16y ago
    You saw benefit because you implemented a custom allocator whose behavior was optimized to the memory access pattern that you planned to use with it. Any decent implementation of malloc already allocates large chunks of contiguous memory from the operating system and tries to maintain locality among allocations. It's also possible that you saw performance improvement from the removal of a function call - it's possible that the call to your custom allocator could be inlined, whereas malloc has to be a function call. My understanding of halloc and talloc is that they are general purpose allocators. A pure library approach - that is, without source code analysis and code generation - won't be able to tailor the allocation scheme based on the data structures themselves.
    - latitude 16y ago
      FooBarWidget got a good point though. When two blocks are explictly tied into a parent-child relationship, it gives the allocator valuable locality information. It is another matter that halloc separates allocation and block binding steps, so the relationship information is not available at the allocation time, and so it cannot utilize these locality hints.
lobster_johnson 16y ago
I suspect the idea behind the library is not performance optimization, but convenience. It's sometimes much more convenient to let someone track allocation dependencies than doing it yourself.
latitude 16y ago
You appear to be mixing two things here. What you described is a form of a "slab allocator" whereby all blocks in a certain size range are allocated from one big piece of memory that is sliced into equally sized chunks. This is really fast, it works great for smaller blocks and it is the way to speed up the STL-heavy code. I did some profiling a while back and a lock-free slab allocator delivered 10x speed up in the code that operated with std::map and strings. The second thing is locality. An allocator like halloc could theoretically utilize the fact that two blocks are explictly marked as related and allocate them close to each other. However, for this to work the allocation function needs to be passed a pointer to the parent block, which is not the case with halloc. So the API needs to change, the implementation needs to change too, and then it will no longer be a light implementation of a simple idea, but something else.

alexgartrell 16y ago

Thank you! Halloc works great for Mongrel2 http://mongrel2.org/dir?ci=4ff647658e12c6f4&name=src/mem http://mongrel2.org/dir?ci=4ff647658e12c6f4&name=src/mem edited to add (for third parties): iirc, halloc is mainly used by mongrel2 in things like the routes table, where it makes the code for maintaining the trie much cleaner.

lobster_johnson 16y ago

So it's like NSZone in Objective-C. In Obj-C you can associate any allocated object instance with a zone (unless you want to use the default, runtime-provided zone); deallocating a zone will also deallocate all the instances. Useful for things like trees where you can deallocate every node just by deallocating the root.