10 comments

  • hinkley 2 hours ago
    I have to say I was always on the fence about Bill Pugh (Mr Skiplist).

    Some of his concurrency ideas were pretty good but Skip Lists were about the same time I was realizing that theoretical and practical design for performance had diverged and skip lists were a huge cache miss liability.

    It didn't hurt that a few people I was aware had tried them had gone back to something else due to live performance analysis being negative or inconclusive (If you can't prove one thing is better than the other, you use the simpler one, and skiplists are not simple)

    • infamouscow 2 hours ago
      B+tree were designed around optimized IO in the era of magnetic storage, they're inherently cache-friendly. Skiplists are the same thing as a b+tree but the structure is inverted, which makes skiplists more to concurrent writer-friendly than b+trees. Different tradeoffs.
      • hinkley 1 hour ago
        But more cache misses, due to the variable pointer length structure.

        That cost varies from chip generation to generation, but it does seem to be the case that b trees win in more generations than they lose.

  • tyre 2 hours ago
    Tangentially related, the PR sections for the final PR in this feature is quite nice[0].

    There is a reviewing guide with suggested reading order, clear design decisions, and scope boundaries for what is intentionally not included.

    This is the type of thing LLMs are very good at and high ROI for human reviewers.

    [0]: https://github.com/valkey-io/valkey/pull/4206

    • pastel8739 2 hours ago
      You really think that LLMs are “very good” at producing useful PR descriptions? I have had a very different experience.
      • stuaxo 1 hour ago
        OMG, I hate the LLM PR descriptions, the comments, the docstrings - anything to be read by a human that isn't code.
      • darig 1 hour ago
        [dead]
  • rsalus 42 minutes ago
    I've long since moved to the MultiQueue algorithm for CPQs, seems like SkipList has vanishingly few use cases now...
  • reconditerose 3 days ago
    Redis historically used a skiplist to keep a sorted index. Valkey showed its inefficient and slow on modern hardware, migrating to a B+ tree instead.
    • hinkley 2 hours ago
      It all ends up back at B trees. Why does it always end up back at B trees?

      At this point have we optimized hardware to assume B trees in a sort of self-fulfilling prophesy?

      • crest 1 hour ago
        Binary trees have worse cache locality. The cost of accessing memory has grown so much compared to computation that supposedly slower "heavy weight" data structures are worth it now (as in the last 10-20 years).
        • eventualcomp 1 hour ago
          A b-tree isn't a binary tree. B doesn't officially stand for binary either, see History[0].

          [0] https://en.wikipedia.org/wiki/B-tree

          • jjmarr 1 hour ago
            I'm guessing their point is unlike binary trees which have two children per node, B trees can have as many children per node is best for cache locality/SIMD/etc. Which despite being "heavyweight" (wasted space if not all children per node are occupied) is faster in practice because it's cheaper to preload large unused blocks to cache rather than only access memory when it is needed.
            • entrope 23 minutes ago
              Every node in a binary tree needs a value and two child pointers, though. That's asymptotically almost twice as many child pointers per value as a B-tree has.
      • alfiedotwtf 1 hour ago
        B trees are more friendly to being cache oblivious
      • wrs 2 hours ago
        Yes, that hardware is called "the memory cache". B-trees were invented because disk reads were very expensive. Now, memory cache fills are very expensive.
    • tyre 2 hours ago
      Is this AI? Why do we need a summary of the actual article in a comment?
      • bertonvv 2 hours ago
        From what I've seen on here many commenters didn't read the article, only the title (I've been guilty of this too). OP is maybe just adapting to HN culture.
        • hinkley 1 hour ago
          There aren't many commenters at the time you posted this. Which makes this conversation feel even more artificial...
          • bertonvv 54 minutes ago
            I meant in general on this site. Dislike the insinuation that I'm generative AI.
      • WD-42 2 hours ago
        The actual article is AI too so this is just saving you time.
  • dnchdnd 2 hours ago
    Is valkey the recommended redis alternative these days ?
    • TkTech 1 hour ago
      Like all things, it depends. If you don't need the latest and greatest features in upstream redis, and you don't want license headaches, Valkey is probably a good default. It's generally cheaper on hosting providers too - AWS will discount you ~20-35% for Valkey vs Redis.
    • swingboy 1 hour ago
      Yes
  • vivzkestrel 54 minutes ago
    - valkey vs redis vs dragonfly 2027?
  • snissn 2 hours ago
    Do they provide their benchmark code?
  • WD-42 2 hours ago
    As a coding exercise I implemented a redis that utilized skiplists. I was excited to read this article. Turns out it's ai slop. Seriously people, stop it. This hurts to read.
  • yoy0721 10 minutes ago
    [flagged]
  • dropdropteam 2 hours ago
    [flagged]