Monday, September 26, 2016

About Skip List

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

7 comments:

  1. 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') ;-)
    Just 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

    ReplyDelete
    Replies
    1. @Manuel
      I 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.

      Delete
  2. @Alfred:
    Already noticed Con's latest innovation?
    "MuQSS"
    What's your opinion?

    BR, Manuel Krause

    ReplyDelete
    Replies
    1. The MuQSS 103 works o.k. on my machine.
      Remembering, 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

      Delete
    2. @Manuel
      I 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

      Delete
    3. @Alfred:
      Version 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

      Delete
    4. 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... ;-)
      BR, Manuel Krause

      Delete