[Lumiera] [Fwd: Re: Any suggestions?]

[Christian Thaeter]

percy tiglao wrote:
>> Well the challenge is now that I want elements as small as a single
>> pointer, its a memory pool and its going to be used to *many* small
>> elements. Maybe an option would be to release this constraint to 2
>> pointers, but no more. Then I would like to maintain the excellent
>> performance of alloc/free O(1) with somewhat more cost or at worst O(log
>> N). So that are the rules of the game (well if you are interested only,
>> I can keep the current implementation, just out of curiosity maybe
>> someone knows something better)
> 
> With two pointers, one can make a tree structure directly. A heap generally
> requires a "parent" pointer, so I'm not sure if that can be done with only two
> pointers. So... if you push it to three pointers... I know you can do every
> operation in O(log N) time trivially. (Heaps do not have the "binary search"
> capacity, so finding an arbitrary node will take O(n) time).
> 
> With only two pointers, Allocations will still only take O(log(n)) time. A "pop"
> from a heap is a heapify-down operation, so you start at the parent and work
> your way down. No need to find the parent, only the children. Deallocations
> can take O(log(n)) time if you can think of a O(1) way of finding the path
> to the "last" element...
> 
> And I think you can do that with precisely one integer. Now, I'm
> getting "creative"
> here, so this may not work. But... here's my reasoning. Any path in the
> tree can be seen as a binary number (0 for left, 1 for right).
> Basically Huffman
> encoding. Heaps are also complete, so if we know the size of the heap, then
> we innately know the path to the last element in the heap (ie: the rightmost
> element in the bottom row). For example, the last element in a tree of size
> 1 is the root. The last element of a tree of size 2 is the left child
> of the root.
> The last element of a tree of size 3 is the right child of the root. Size 10 is
> left, right, left... and size 100 is right, left, left, right, left,
> left. The way to get
> this number is simply to read off the binary digits and ignore the
> first non-zero
> bit. (110 0100 is "one hundred" in binary. 1 is right, 0 is left).
> 
> And, deallocations is just adding an element into the heap, and then
> heapifying up. So you just need to add to the (1+size) position to push an
> element into the list. (And a deallocation will always put the next element into
> the (1+size) position). So yes, it does seem like two pointers can suffice
> for O(log(n)) time allocations and deallocations with a heap structure.
> There is some creativity involved with finding the path quickly... but as
> long as you keep the size of the list.
> 
> Finding the parents to do the heapify-up operation will take O(log(n))
> (instead of O(1) in an array form), but if the parents are saved and not
> recomputed every time needed during the heapify-up, you can keep
> O(log(n)) deallocation time. So a bit of careful coding is needed here.
> 
> Total cost of this scheme: two pointers per node, a pointer to the root
> of the heap, and one integer to keep track of the size. O(log(n)) allocations
> and O(log(n)) deallocations, and the allocations will _always_ return the
> smallest memory location available.
> 
> Does that fit the bill?

Yes, looks clever.. i'll try that too. btw i do such a 'path keeping'
already in the splay tree implementation.

Thinking further about it, even the optimization/shrink operation will
be doable by running a heapsort, building a fully sorted heap and maybe
move elements to the front.

	Thanks,
		Christian

> 
> -- Percy