I read one post about skip list today which link to this web(
http://ticki.github.io/blog/skip-lists-done-right/), in which some very useful information can be found.
The "O(1) level generation" is just what I used in my new skiplist implement in BFS, though I never read similar before.
BR Alfred
This is quite a very short note from yours, for such a huge scientific topic. Reminds me of my studies, decades ago. No, NOT informatics (formally known as 'computer science') ;-)
ReplyDeleteJust need some days/ maybe a week to work into the terms, that are used there, to understand at least a bit.
Con Kolivas also posted several things and links about Skiplists, so far. Especially, when he newly took up the topic. The following are known:
http://ck-hack.blogspot.de/2011/09/bfs-and-skip-lists.html -- Con's first description
https://lkml.org/lkml/2011/9/23/371 -- Con's posting to LKML regarding Skiplists
https://en.wikipedia.org/wiki/Skip_list -- Con's mentioning of wikipedia's Skiplist entry
and of course,
http://ck-hack.blogspot.de/2016/09/bfs-480-linux-47-ck2.html -- Con describing his new approach for BFS480+
where he writes down, "(...) This now means that BFS is no longer O(n) lookup after O(1) insertion. It is now O(log(n)) insertion, O(1) lookup and O(k) removal where k <= 16, thereby tackling a long-standing criticism of the overall design. (...)"
I don't understand it atm., but want to know from you anyways, Alfred, how much is the difference of your current work to Con's.
Coming to my mind is the picture of someone re-inventing the wheel. This shouldn't sound impolitely in any way, it's just meant as question. Maybe you've advanced from that level.
BR Manuel Krause
@Manuel
DeleteI post this just for information to who intersting in. Unlike other paper document, I think this link is easier to read and contains useful information. I highlighted the level generation because same implementation is used in my skiplist work.
My work are mainly trying to fix the concerns in my prevous post(http://cchalpha.blogspot.com/2016/09/about-skip-list-in-bfs.html), but in order to do that, most code are rewriten.
I don't think it is a "re-inventing the wheel" thing here, just a better implementation.
@Alfred:
ReplyDeleteAlready noticed Con's latest innovation?
"MuQSS"
What's your opinion?
BR, Manuel Krause
The MuQSS 103 works o.k. on my machine.
DeleteRemembering, that already the -gc patches made a great improvement upon Con's latest evolution, I'm looking forward to your re-newed addons for MuQSS. (In the hope that you still follow Con's BFS/MuQSS path.)
BR, happy analyzing & developing,
Manuel Krause
@Manuel
DeleteI will look deep into MuQSS as I am on vocation。 First impressions about MuQSS is it's similar to the preempt task design in VRQ and replace the preempt task with a skip_list to hold more tasks. The balance issue is my first concern as global run queue has been removed, which is the foundational balance design in BFS.
BR Alfred
@Alfred:
DeleteVersion 105 of MuQSS is even more mature, now. Quite a fine and fast evolution, in my eyes.
Depending on the point of view, good or bad that I've changed my testing circumstances, yesterday I've invested some time to severely calm down my firefox by adding many more ad blocking rules. Looks like I'd never reach annoying cpu usage peaks of in-firefox flash video playback any more = good, and wouldn't be able to compare current testing with that of the last months = bad.
My best wishes for your vacation, and don't forget to relax ^^
BR, Manuel Krause
Even a newer revision, 106, is available now, that maybe changes some algorithms. Just, to keep you up to date, and in case, you have too much spare time... ;-)
DeleteBR, Manuel Krause