6 ms·

If I read the code correctly, ta_free() is O(n), whereby n is a number of allocated blocks. That's not very good. PS. Also the block alignment is aligning the

by abcd_f 8y ago

If I read the code correctly, ta_free() is O(n), whereby n is a number of allocated blocks. That's not very good. PS. Also the block alignment is aligning the wrong thing. It should be aligning the start of the public (returned) part, not the block size and that's done by padding Block struct as required (if required)... and not to the hardcoded 8 bytes. Otherwise you'll get SIGBUS on RISC boxes. PPS. At the risk of stating the obvious, this is nothing more than a toy allocator, with lots of loose ends. A lab exercise in a second-third year of an average CS course - maybe, but this is not something suitable for production. Perhaps it works for some specific cases, but these aren't specified. So seeing this massively upvoted and at the top of HN is a bit strange.

ChuckMcM 8y ago
And this: Also, allocation will fail when all blocks in the fixed size block array are used, even though there might still be ample space in the heap memory region... Basically you can fail memory allocation with a lot of small allocations that aren't using all of a block. This situation bit me when using some C++ code on a Cortex-M class processor where the C++ code ended up creating a bunch of objects with very small allocations in them. That said, the code is pretty clean and easy to read so its a pretty understandable allocator. Some malloc implementations are so opaque you have to study them for a week to tease out how they work.
toxmeister 8y ago
Hey, author here - this post/thread completely hit my by surprise, so apols for late reply: 1) ta_free() is only O(n) if block compaction is enabled, else it's O(1), i.e. a simple cons of the freed block addr to the free list (https://github.com/thi-ng/tinyalloc/blob/master/tinyalloc.c#L84 https://github.com/thi-ng/tinyalloc/blob/master/tinyalloc.c#...) 2) there's no hardcoded alignment (it's configurable via TA_ALIGN macro) and I'm confused about your other comment about not aligning the right address in general. that's a wrong observation and i think you misunderstood the diagram in the readme. 3) it's clearly stated in the readme that this is largely meant for memory constrained situations (or where not large numbers of blocks, realloc or multithreading is needed/available) and so it's not meant to be a replacement for dlmalloc / jemalloc caliber allocators etc. i needed something small & lightweight and it did it's job very well in several production projects on the ARM STM32 platform (where I have upto around 8MB managed). I also found it very useful for some ongoing JS/WASM interop projects (i.e. there's JS version here: https://github.com/thi-ng/umbrella/blob/master/packages/malloc/README.md https://github.com/thi-ng/umbrella/blob/master/packages/mall...)

by abcd_f 8y ago

ChuckMcM 8y ago

And this: Also, allocation will fail when all blocks in the fixed size block array are used, even though there might still be ample space in the heap memory region... Basically you can fail memory allocation with a lot of small allocations that aren't using all of a block. This situation bit me when using some C++ code on a Cortex-M class processor where the C++ code ended up creating a bunch of objects with very small allocations in them. That said, the code is pretty clean and easy to read so its a pretty understandable allocator. Some malloc implementations are so opaque you have to study them for a week to tease out how they work.

toxmeister 8y ago

Hey, author here - this post/thread completely hit my by surprise, so apols for late reply: 1) ta_free() is only O(n) if block compaction is enabled, else it's O(1), i.e. a simple cons of the freed block addr to the free list (https://github.com/thi-ng/tinyalloc/blob/master/tinyalloc.c#L84 https://github.com/thi-ng/tinyalloc/blob/master/tinyalloc.c#...) 2) there's no hardcoded alignment (it's configurable via TA_ALIGN macro) and I'm confused about your other comment about not aligning the right address in general. that's a wrong observation and i think you misunderstood the diagram in the readme. 3) it's clearly stated in the readme that this is largely meant for memory constrained situations (or where not large numbers of blocks, realloc or multithreading is needed/available) and so it's not meant to be a replacement for dlmalloc / jemalloc caliber allocators etc. i needed something small & lightweight and it did it's job very well in several production projects on the ARM STM32 platform (where I have upto around 8MB managed). I also found it very useful for some ongoing JS/WASM interop projects (i.e. there's JS version here: https://github.com/thi-ng/umbrella/blob/master/packages/malloc/README.md https://github.com/thi-ng/umbrella/blob/master/packages/mall...)