7 added 337 characters in body
source | link

To me if you are going to add "batch" support to a free list which can also allocate smaller chunks, the point is not to allocate the batch more quickly than allocating kBatchSize elements individually through the free list. It's to have contiguity guarantees on the result as would be necessary to implement a small contiguous sequence using it, e.g.

The work required for allocating and freeing from a free list is already so trivial that there aren't any reasonable speed improvements to be had by batching, but individually allocating single elements from a free list doesn't give you those contiguity guarantees.

As for how you'd optimally implement it, I can't say, but this might be an important hint. Personally I'd rather just use the parent allocator in these cases or just use a separate free list that's designed to allocate kMaxSize*kBatchSize byte chunks.

In my humble opinion Alexandrescu is a hit-n-miss type as with the case of many genius pioneers pushing the boundaries of a programming language. His ideas range from brilliant and widely applicable to unwieldly and impractical. If I was to consider batch support for a free list, the first thing I'd consider is another free list or a different allocator outright. Besides that, an allocator with 5 template parameters is already pretty cumbersome to use. The idea of being able to specify parent allocators is a marvelous idea I want to steal. Not so sure about specifying min/max sizes, batch sizes, and upper bounds. Dunno, maybe he'll astound me by showing off a super efficient and simple implementation that eludes me for this. At the moment I can't see one, and I thought about it for an hour since I first answered this.

So much of the uber simplicity and blazing speed of free lists comes from the narrowing assumption that they are fixed-sized allocators, not variable-sized ones, and that each chunk can serve as a union of used memory for the particular element type or a singly-linked list pointer to the next free chunk (for which it's crucial that the chunks are all the same size to trivialize the deallocation logic while still allowing the freed memory to be reclaimed in its entirety upon subsequent allocations). The ability to allocate in batches throws a monkey wrench into the concept for which I don't think there's any solution that can achieve the same speed for all input cases.

Attempt

Ugh, this question had me thinking for so long about it as well as visiting the whiteboard and tossing away idea after idea.

The only ideas I've had so far that come close to being able to achieve all desired operations in constant-time with batch allocation support in there requires metadata to be associated with the allocation and some assumptions to be made about exactly how the memory pools the chunks are pooled from align (with huge alignments used for the pools) to allow us to get from a pointer to the chunk back to the pool to get access to the metadata using some arithmetic.

The memory overhead can be very small, less than 1 byte per chunk (just the length of the batch) unless kBatchSize is huge (which it shouldn't be anyway or else we should probably use parent allocator), but it'll also require an array of kBatchSize free head pointers to be stored in the allocator itself.

I can almost picture the solution but I don't like where it's headed because providing batch support to a free list isn't a practical enough use case to justify all this work (both mentally and computationally) unless there's some magically simple and beautiful solution that's eluding us which incurs zero cost for the common cases.

To me if you are going to add "batch" support to a free list which can also allocate smaller chunks, the point is not to allocate the batch more quickly than allocating kBatchSize elements individually through the free list. It's to have contiguity guarantees on the result as would be necessary to implement a small contiguous sequence using it, e.g.

The work required for allocating and freeing from a free list is already so trivial that there aren't any reasonable speed improvements to be had by batching, but individually allocating single elements from a free list doesn't give you those contiguity guarantees.

As for how you'd optimally implement it, I can't say, but this might be an important hint. Personally I'd rather just use the parent allocator in these cases or just use a separate free list that's designed to allocate kMaxSize*kBatchSize byte chunks.

In my humble opinion Alexandrescu is a hit-n-miss type as with the case of many genius pioneers pushing the boundaries of a programming language. His ideas range from brilliant and widely applicable to unwieldly and impractical. If I was to consider batch support for a free list, the first thing I'd consider is another free list or a different allocator outright. Besides that, an allocator with 5 template parameters is already pretty cumbersome to use. The idea of being able to specify parent allocators is a marvelous idea I want to steal. Not so sure about specifying min/max sizes, batch sizes, and upper bounds. Dunno, maybe he'll astound me by showing off a super efficient and simple implementation that eludes me for this. At the moment I can't see one, and I thought about it for an hour since I first answered this.

So much of the uber simplicity and blazing speed of free lists comes from the narrowing assumption that they are fixed-sized allocators, not variable-sized ones, and that each chunk can serve as a union of used memory for the particular element type or a singly-linked list pointer to the next free chunk (for which it's crucial that the chunks are all the same size to trivialize the deallocation logic while still allowing the freed memory to be reclaimed in its entirety upon subsequent allocations). The ability to allocate in batches throws a monkey wrench into the concept for which I don't think there's any solution that can achieve the same speed for all input cases.

Attempt

Ugh, this question had me thinking for so long about it as well as visiting the whiteboard and tossing away idea after idea.

The only ideas I've had so far that come close to being able to achieve all desired operations in constant-time with batch allocation support in there requires metadata to be associated with the allocation and some assumptions to be made about exactly how the memory pools the chunks are pooled from align (with huge alignments used for the pools) to allow us to get from a pointer to the chunk back to the pool to get access to the metadata using some arithmetic.

The memory overhead can be very small, less than 1 byte per chunk unless kBatchSize is huge (which it shouldn't be anyway or else we should probably use parent allocator), but it'll also require an array of kBatchSize free head pointers to be stored in the allocator itself.

To me if you are going to add "batch" support to a free list which can also allocate smaller chunks, the point is not to allocate the batch more quickly than allocating kBatchSize elements individually through the free list. It's to have contiguity guarantees on the result as would be necessary to implement a small contiguous sequence using it, e.g.

The work required for allocating and freeing from a free list is already so trivial that there aren't any reasonable speed improvements to be had by batching, but individually allocating single elements from a free list doesn't give you those contiguity guarantees.

As for how you'd optimally implement it, I can't say, but this might be an important hint. Personally I'd rather just use the parent allocator in these cases or just use a separate free list that's designed to allocate kMaxSize*kBatchSize byte chunks.

In my humble opinion Alexandrescu is a hit-n-miss type as with the case of many genius pioneers pushing the boundaries of a programming language. His ideas range from brilliant and widely applicable to unwieldly and impractical. If I was to consider batch support for a free list, the first thing I'd consider is another free list or a different allocator outright. Besides that, an allocator with 5 template parameters is already pretty cumbersome to use. The idea of being able to specify parent allocators is a marvelous idea I want to steal. Not so sure about specifying min/max sizes, batch sizes, and upper bounds. Dunno, maybe he'll astound me by showing off a super efficient and simple implementation that eludes me for this. At the moment I can't see one, and I thought about it for an hour since I first answered this.

So much of the uber simplicity and blazing speed of free lists comes from the narrowing assumption that they are fixed-sized allocators, not variable-sized ones, and that each chunk can serve as a union of used memory for the particular element type or a singly-linked list pointer to the next free chunk (for which it's crucial that the chunks are all the same size to trivialize the deallocation logic while still allowing the freed memory to be reclaimed in its entirety upon subsequent allocations). The ability to allocate in batches throws a monkey wrench into the concept for which I don't think there's any solution that can achieve the same speed for all input cases.

Attempt

Ugh, this question had me thinking for so long about it as well as visiting the whiteboard and tossing away idea after idea.

The only ideas I've had so far that come close to being able to achieve all desired operations in constant-time with batch allocation support in there requires metadata to be associated with the allocation and some assumptions to be made about exactly how the memory pools the chunks are pooled from align (with huge alignments used for the pools) to allow us to get from a pointer to the chunk back to the pool to get access to the metadata using some arithmetic.

The memory overhead can be very small, less than 1 byte per chunk (just the length of the batch) unless kBatchSize is huge (which it shouldn't be anyway or else we should probably use parent allocator), but it'll also require an array of kBatchSize free head pointers to be stored in the allocator itself.

I can almost picture the solution but I don't like where it's headed because providing batch support to a free list isn't a practical enough use case to justify all this work (both mentally and computationally) unless there's some magically simple and beautiful solution that's eluding us which incurs zero cost for the common cases.

6 added 495 characters in body
source | link

To me if you are going to add "batch" support to a free list which can also allocate smaller chunks, the point is not to allocate the batch more quickly than allocating kBatchSize elements individually through the free list. It's to have contiguity guarantees on the result as would be necessary to implement a small contiguous sequence using it, e.g.

The work required for allocating and freeing from a free list is already so trivial that there aren't any reasonable speed improvements to be had by batching, but individually allocating single elements from a free list doesn't give you those contiguity guarantees.

As for how you'd optimally implement it, I can't say, but this might be an important hint. Personally I'd rather just use the parent allocator in these cases or just use a separate free list that's designed to allocate kMaxSize*kBatchSize byte chunks.

In my humble opinion Alexandrescu is a hit-n-miss type as with the case of many genius pioneers pushing the boundaries of a programming language. His ideas range from brilliant and widely applicable to unwieldly and impractical. If I was to consider batch support for a free list, the first thing I'd consider is another free list or a different allocator outright. Besides that, an allocator with 5 template parameters is already pretty cumbersome to use. The idea of being able to specify parent allocators is a marvelous idea I want to steal. Not so sure about specifying min/max sizes, batch sizes, and upper bounds. Dunno, maybe he'll astound me by showing off a super efficient and simple implementation that eludes me for this. At the moment I can't see one, and I thought about it for an hour since I first answered this.

So much of the uber simplicity and blazing speed of free lists comes from the narrowing assumption that they are fixed-sized allocators, not variable-sized ones, and that each chunk can serve as a union of used memory for the particular element type or a singly-linked list pointer to the next free chunk (for which it's crucial that the chunks are all the same size to trivialize the deallocation logic while still allowing the freed memory to be reclaimed in its entirety upon subsequent allocations). The ability to allocate in batches throws a monkey wrench into the concept for which I don't think there's any solution that can achieve the same speed for all input cases.

Attempt

Ugh, this question had me thinking for so long about it as well as visiting the whiteboard and tossing away idea after idea.

The only ideas I've had so far that come close to being able to achieve all desired operations in constant-time with batch allocation support in there requires metadata to be associated with the allocation and some assumptions to be made about exactly how the memory pools the chunks are pooled from align (with huge alignments used for the pools) to allow us to get from a pointer to the chunk back to the pool to get access to the metadata using some arithmetic.

The memory overhead can be very small, less than 1 byte per chunk unless kBatchSize is huge (which it shouldn't be anyway or else we should probably use parent allocator), but it'll also require an array of kBatchSize free head pointers to be stored in the allocator itself.

To me if you are going to add "batch" support to a free list which can also allocate smaller chunks, the point is not to allocate the batch more quickly than allocating kBatchSize elements individually through the free list. It's to have contiguity guarantees on the result as would be necessary to implement a small contiguous sequence using it, e.g.

The work required for allocating and freeing from a free list is already so trivial that there aren't any reasonable speed improvements to be had by batching, but individually allocating single elements from a free list doesn't give you those contiguity guarantees.

As for how you'd optimally implement it, I can't say, but this might be an important hint. Personally I'd rather just use the parent allocator in these cases or just use a separate free list that's designed to allocate kMaxSize*kBatchSize byte chunks.

In my humble opinion Alexandrescu is a hit-n-miss type as with the case of many genius pioneers pushing the boundaries of a programming language. His ideas range from brilliant and widely applicable to unwieldly and impractical. If I was to consider batch support for a free list, the first thing I'd consider is another free list or a different allocator outright. Besides that, an allocator with 5 template parameters is already pretty cumbersome to use. The idea of being able to specify parent allocators is a marvelous idea I want to steal. Not so sure about specifying min/max sizes, batch sizes, and upper bounds. Dunno, maybe he'll astound me by showing off a super efficient and simple implementation that eludes me for this. At the moment I can't see one, and I thought about it for an hour since I first answered this.

So much of the uber simplicity and blazing speed of free lists comes from the narrowing assumption that they are fixed-sized allocators, not variable-sized ones, and that each chunk can serve as a union of used memory for the particular element type or a singly-linked list pointer to the next free chunk (for which it's crucial that the chunks are all the same size to trivialize the deallocation logic while still allowing the freed memory to be reclaimed in its entirety upon subsequent allocations). The ability to allocate in batches throws a monkey wrench into the concept for which I don't think there's any solution that can achieve the same speed for all input cases.

To me if you are going to add "batch" support to a free list which can also allocate smaller chunks, the point is not to allocate the batch more quickly than allocating kBatchSize elements individually through the free list. It's to have contiguity guarantees on the result as would be necessary to implement a small contiguous sequence using it, e.g.

The work required for allocating and freeing from a free list is already so trivial that there aren't any reasonable speed improvements to be had by batching, but individually allocating single elements from a free list doesn't give you those contiguity guarantees.

As for how you'd optimally implement it, I can't say, but this might be an important hint. Personally I'd rather just use the parent allocator in these cases or just use a separate free list that's designed to allocate kMaxSize*kBatchSize byte chunks.

In my humble opinion Alexandrescu is a hit-n-miss type as with the case of many genius pioneers pushing the boundaries of a programming language. His ideas range from brilliant and widely applicable to unwieldly and impractical. If I was to consider batch support for a free list, the first thing I'd consider is another free list or a different allocator outright. Besides that, an allocator with 5 template parameters is already pretty cumbersome to use. The idea of being able to specify parent allocators is a marvelous idea I want to steal. Not so sure about specifying min/max sizes, batch sizes, and upper bounds. Dunno, maybe he'll astound me by showing off a super efficient and simple implementation that eludes me for this. At the moment I can't see one, and I thought about it for an hour since I first answered this.

So much of the uber simplicity and blazing speed of free lists comes from the narrowing assumption that they are fixed-sized allocators, not variable-sized ones, and that each chunk can serve as a union of used memory for the particular element type or a singly-linked list pointer to the next free chunk (for which it's crucial that the chunks are all the same size to trivialize the deallocation logic while still allowing the freed memory to be reclaimed in its entirety upon subsequent allocations). The ability to allocate in batches throws a monkey wrench into the concept for which I don't think there's any solution that can achieve the same speed for all input cases.

Attempt

Ugh, this question had me thinking for so long about it as well as visiting the whiteboard and tossing away idea after idea.

The only ideas I've had so far that come close to being able to achieve all desired operations in constant-time with batch allocation support in there requires metadata to be associated with the allocation and some assumptions to be made about exactly how the memory pools the chunks are pooled from align (with huge alignments used for the pools) to allow us to get from a pointer to the chunk back to the pool to get access to the metadata using some arithmetic.

The memory overhead can be very small, less than 1 byte per chunk unless kBatchSize is huge (which it shouldn't be anyway or else we should probably use parent allocator), but it'll also require an array of kBatchSize free head pointers to be stored in the allocator itself.

5 added 209 characters in body
source | link

To me if you are going to add "batch" support to a free list which can also allocate smaller chunks, the point is not to allocate the batch more quickly than allocating kBatchSize elements individually through the free list. It's to have contiguity guarantees on the result as would be necessary to implement a small contiguous sequence using it, e.g.

The work required for allocating and freeing from a free list is already so trivial that there aren't any reasonable speed improvements to be had by batching, but individually allocating single elements from a free list doesn't give you those contiguity guarantees.

As for how you'd optimally implement it, I can't say, but this might be an important hint. Personally I'd rather just use the parent allocator in these cases or just use a separate free list that's designed to allocate kMaxSize*kBatchSize byte chunks.

In my humble opinion Alexandrescu is a hit-n-miss type as with the case of many genius pioneers pushing the boundaries of a programming language. His ideas range from brilliant and widely applicable to unwieldly and impractical. If I was to consider batch support for a free list, the first thing I'd consider is another free list or a different allocator outright. Besides that, an allocator with 5 template parameters is already pretty cumbersome to use. The idea of being able to specify parent allocators is a marvelous idea I want to steal. Not so sure about specifying min/max sizes, batch sizes, and upper bounds. Dunno, maybe he'll astound me by showing off a super efficient and simple implementation that eludes me for this. At the moment I can't see one, and I thought about it for an hour since I first answered this.

So much of the uber simplicity and blazing speed of free lists comes from the narrowing assumption that they are fixed-sized allocators, not variable-sized ones, and that each chunk can serve as a union of used memory for the particular element type or a singly-linked list pointer to the next free chunk (for which it's crucial that the chunks are all the same size to trivialize the deallocation logic while still allowing the freed memory to be reclaimed in its entirety upon subsequent allocations). The ability to allocate in batches throws a monkey wrench into the concept for which I don't think there's any solution that can achieve the same speed for all input cases.

To me if you are going to add "batch" support to a free list which can also allocate smaller chunks, the point is not to allocate the batch more quickly than allocating kBatchSize elements individually through the free list. It's to have contiguity guarantees on the result as would be necessary to implement a small contiguous sequence using it, e.g.

The work required for allocating and freeing from a free list is already so trivial that there aren't any reasonable speed improvements to be had by batching, but individually allocating single elements from a free list doesn't give you those contiguity guarantees.

As for how you'd optimally implement it, I can't say, but this might be an important hint. Personally I'd rather just use the parent allocator in these cases or just use a separate free list that's designed to allocate kMaxSize*kBatchSize byte chunks.

In my humble opinion Alexandrescu is a hit-n-miss type as with the case of many genius pioneers pushing the boundaries of a programming language. His ideas range from brilliant and widely applicable to unwieldly and impractical. If I was to consider batch support for a free list, the first thing I'd consider is another free list or a different allocator outright. Besides that, an allocator with 5 template parameters is already pretty cumbersome to use. The idea of being able to specify parent allocators is a marvelous idea I want to steal. Not so sure about specifying min/max sizes, batch sizes, and upper bounds.

So much of the uber simplicity and blazing speed of free lists comes from the narrowing assumption that they are fixed-sized allocators, not variable-sized ones, and that each chunk can serve as a union of used memory for the particular element type or a singly-linked list pointer to the next free chunk (for which it's crucial that the chunks are all the same size to trivialize the deallocation logic while still allowing the freed memory to be reclaimed in its entirety upon subsequent allocations). The ability to allocate in batches throws a monkey wrench into the concept for which I don't think there's any solution that can achieve the same speed for all input cases.

To me if you are going to add "batch" support to a free list which can also allocate smaller chunks, the point is not to allocate the batch more quickly than allocating kBatchSize elements individually through the free list. It's to have contiguity guarantees on the result as would be necessary to implement a small contiguous sequence using it, e.g.

The work required for allocating and freeing from a free list is already so trivial that there aren't any reasonable speed improvements to be had by batching, but individually allocating single elements from a free list doesn't give you those contiguity guarantees.

As for how you'd optimally implement it, I can't say, but this might be an important hint. Personally I'd rather just use the parent allocator in these cases or just use a separate free list that's designed to allocate kMaxSize*kBatchSize byte chunks.

In my humble opinion Alexandrescu is a hit-n-miss type as with the case of many genius pioneers pushing the boundaries of a programming language. His ideas range from brilliant and widely applicable to unwieldly and impractical. If I was to consider batch support for a free list, the first thing I'd consider is another free list or a different allocator outright. Besides that, an allocator with 5 template parameters is already pretty cumbersome to use. The idea of being able to specify parent allocators is a marvelous idea I want to steal. Not so sure about specifying min/max sizes, batch sizes, and upper bounds. Dunno, maybe he'll astound me by showing off a super efficient and simple implementation that eludes me for this. At the moment I can't see one, and I thought about it for an hour since I first answered this.

So much of the uber simplicity and blazing speed of free lists comes from the narrowing assumption that they are fixed-sized allocators, not variable-sized ones, and that each chunk can serve as a union of used memory for the particular element type or a singly-linked list pointer to the next free chunk (for which it's crucial that the chunks are all the same size to trivialize the deallocation logic while still allowing the freed memory to be reclaimed in its entirety upon subsequent allocations). The ability to allocate in batches throws a monkey wrench into the concept for which I don't think there's any solution that can achieve the same speed for all input cases.

4 added 465 characters in body
source | link
3 added 164 characters in body
source | link
2 added 83 characters in body
source | link
1
source | link