Re: Joy of this, Joy of that

The Natural Philosopher <tnp@invalid.invalid> writes:

On 28/11/2024 14:19, Rich wrote:

For performance reasons you'd want to maintain some index data
structure that can be searched faster than O(N), which becomes
additional overhead for the malloc's and for free.  As well, as Richard
K.  also says in his posts, just that is not enough to track and ignore
all double free operations.  Which adds on even more overhead.

 
Its not hard to do a binary search on an ordered linked list, and its
a piece if piss to insert to make it ordered

Binary search on a doubly linked list would have O(n) time
complexity. For a singly linked list, you’re looking at more like
O(n.log n). Both would have truly terribly cache behavior, further
impacting performance.

A linear search would actually be faster than this proposal.  The right
answer is a balanced tree or a hash table.

--
https://www.greenend.org.uk/rjk/