Re: [boost] [graph][heap][coroutine] interruptable dijkstra shortest path function

Subject: Re: [boost] [graph][heap][coroutine] interruptable dijkstra shortest path function
From: Alex Hagen-Zanker (ahh34_at_[hidden])
Date: 2012-09-26 11:01:18

On 26/09/2012 10:37, Rob Stewart wrote:
> On Sep 24, 2012, at 11:27 AM, Alex Hagen-Zanker <ahh34_at_[hidden]> wrote:
>
>> On 24/09/2012 14:25, Rob Stewart wrote:
>>> On Sep 24, 2012, at 7:07 AM, Alex Hagen-Zanker <ahh34_at_[hidden]> wrote:
>>>
>>>> I am just interested to see the fundamental difference between the Boost.Graph d_ary_heap and Boost.Heap d_ary_heap. Because the statement that Graph is optimized for integer values does not seem correct. I noticed that Graph manages the handles through an array and Heap through a std::list and considered that there might be some difference in performance because of that.
>>>>
>>>> Probably the difference is minute, but at the same time it is the only place where I see that Graph makes an assumption (the total number of values pushed onto the heap is known) that Heap cannot make.
>>> Locality of reference and a single free store allocation are sufficient reasons for Graph's implementation to be faster. Perhaps a deque would be better than a list for Heap.
>> The single free store allocation does make a difference of course. I don't really understand how locality of reference plays a role. Are both options not equally local?
> No. Lists are node-based, so each element is from a different part of the free store. By contrast, in an array, the elements are in contiguous memory. That difference affects the speed at which the elements can be accessed due to the behaviors of memory, MMUs, and caching.
>
>
I see. That would make the case for using an unordered list which does 
not need to be node based. I gave it a try out of interest, and it did 
neither hurt nor help. 
(http://people.ds.cam.ac.uk/ahh34/unordered_list.hpp).

Which is something similar to this:

std::vector<T> data;
std::vector<size_t> open_slots;

size_t get_handle(T value) {
   if(open_slots.empty() ) {
      data.push_back(value);
      return data.size() -1;
   } else {
    handle = open_slots.back();
    open_slots.pop_back();
    data[handle] = value;
    return handle;
   }
}

value get_value(size_t handle) { return data[handle]; }

void erase(size_t handle)  { open_slots.push_back(handle); }