On Tue, Feb 17, 2009 at 9:12 PM, Monty Taylor <[email protected]> wrote: > Padraig O'Sullivan wrote: >> On Tue, Feb 17, 2009 at 8:32 PM, Monty Taylor <[email protected]> wrote: >>> Padraig O'Sullivan wrote: >>>> On Tue, Feb 17, 2009 at 4:43 PM, Monty Taylor <[email protected]> wrote: >>>>> Padraig O'Sullivan wrote: >>>>>> On Tue, Feb 17, 2009 at 3:22 PM, Monty Taylor <[email protected]> wrote: >>>>>>> Hey Padraig, >>>>>>> >>>>>>> I think you're moving in the right direction so far. Some things to >>>>>>> think about: >>>>>>> >>>>>>> Perhaps if you did: >>>>>>> >>>>>>> class buffpek_compare >>>>>>> { >>>>>>> qsort_cmp2 key_compare; >>>>>>> void *key_compare_arg; >>>>>>> >>>>>>> public: >>>>>>> buffpek_compare(qsort_cmp2 in_key_compare, void* in_compare_arg) >>>>>>> : key_compare(in_key_compare), key_compare_arg(in_compare_arg) { } >>>>>>> inline bool operator()(BUFFPEK *i, BUFFPEK *j) >>>>>>> { >>>>>>> return key_compare(key_compare_arg, >>>>>>> *((unsigned char **) i->key), *((unsigned >>>>>>> char **) j->key)); >>>>>>> } >>>>>>> }; >>>>>>> >>>>>>> instead, you could remove the need for the extra Context struct, since >>>>>>> your function object has its own way to store context. >>>>>> heh, that's interesting. I actually started moving towards the above >>>>>> last night when I was working on this some more. >>>>>> >>>>>>> The next step being to get rid of buffpek_compare all together and >>>>>>> replace the qsort_cmp2 that's passed in with a function object itself >>>>>>> which could be directly handed to std::sort() or to priority_queue as >>>>>>> its sort function param. >>>>>>> >>>>>>> resuse_freed_buff() looks more like memory management "cleverness" that >>>>>>> would be unneeded if you used priority_queue in the first place. It >>>>>>> sounds like you're guessing the same thing already - but good choice to >>>>>>> take it slow and deal with it piece by piece. >>>>>> I've really been wanting to use a priority queue here as you said. The >>>>>> one thing stopping me at the moment is the reuse_freed_buff() >>>>>> function. I had guessed that the function was moving memory from an >>>>>> element that has just been removed from the queue to other elements >>>>>> still in the queue but I wasn't sure. Is that roughly what it does? >>>>>> >>>>>> If you think that reuse_freed_buff() will be un-needed if I switch to >>>>>> a priority queue here then I might just start on that tonight. It >>>>>> should be pretty straightforward to change what I have done now to use >>>>>> a priority queue instead. Sound like a good idea? >>>>> Do it. It sounds like the reuse_freed_buff() is trying to do the same >>>>> thing that the remove_if() algorithm does for vectors... but I think >>>>> we're better off not doing this by hand once we've got priority_queue >>>>> managing that behind the scenes. >>>> I have this done now but there is one thing I want to be sure of. So >>>> the QUEUE in the current implementation is a queue of structures >>>> (BUFFPEK) sorted on a key. A few times in the current code, a re-heap >>>> is explicitly called on the queue - this happens when the key is >>>> changed. The question I have is when does the STL implementation of >>>> priority queue re-heap itself? >>>> >>>> For example, in the current implementation, there is a piece of code like >>>> this: >>>> >>>> top= (BUFFPEK *) queue_top(&queue); >>>> ... >>>> /* >>>> read next key from the cache or from the file and push it to the >>>> queue; this gives new top. >>>> */ >>>> top->key+= key_length; >>>> if (--top->mem_count) >>>> queue_replaced(&queue); >>>> >>>> Will the STL implementation of priority queue re-heap itself after the >>>> key is changed here? Or does it only re-heap itself after elements are >>>> inserted and removed? >>> If you change the struct that an element of the priority queue is >>> pointing to, it will not, AIUI, re-heap. >> >> Yeah, you're right. I threw together a simple test case which exhibits >> this behavior i.e. an element of the priority queue changes but the >> priority queue does not re-heap. >> >> This means I need to think a bit more and make sure the semantics of >> merge_walk() are still correct when I replace QUEUE with priority >> queue. By the way, if I had to re-heap a priority queue here, is there >> a preferred method of doing that? > > Not really. On the other hand - if the element in the queue has > fundamentally changed, is the priority_queue really the right thing to > manage those objects? I'd say no.
Good point. I'm going to finish this implementation with priority queue and write up what I've done on the blueprint specification. We can see then whether priority queue is a good fit in this situation or not. > > OTOH, if you take your code from above and make it: > > top= queue.pop(); > > /* > read next key from the cache or from the file and push it to the > queue; this gives new top. > */ > top->key+= key_length; > if (--top->mem_count) > queue.push(top); > > Then it should work, no? That won't exactly work here but you gave me an idea for an alternative solution based on the above. Again. I'll put all this in the blueprint specification (probably tomorrow night) and push my branch so you can have a look at it. > >>> Perhaps: >>> http://www.cplusplus.com/reference/stl/priority_queue/push.html >>> and then >>> http://www.cplusplus.com/reference/algorithm/push_heap.html >>> >>> May give more details ...(in case I'm not reading your question correctly) >>> >>> Monyt >>> >>>>>>> Where was the tree you had the changes in again? >>>>>> Its in lp:~posulliv/drizzle/code-cleanup-c++-replace-queue but I >>>>>> havn't pushed my changes to it yet. I've been committing everything I >>>>>> do to my local branch so I'll probably push it to launchpad when I get >>>>>> things a little more cleaned up and am more confident in what I've >>>>>> done. >>>>> Let me know when it's in decent shape and I'll run some performance >>>>> diffs on it. >>>>> >>>>>> Thanks for your input and taking the time to look at what I wrote! >>>>> Thanks for the work. >>>>> >>>>> Monty >>>>> >>>>> >>> >> > > _______________________________________________ Mailing list: https://launchpad.net/~drizzle-discuss Post to : [email protected] Unsubscribe : https://launchpad.net/~drizzle-discuss More help : https://help.launchpad.net/ListHelp
