7 comments

  • tyre 1 hour 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 1 hour ago
      You really think that LLMs are “very good” at producing useful PR descriptions? I have had a very different experience.
      • stuaxo 1 minute ago
        OMG, I hate the LLM PR descriptions, the comments, the docstrings - anything to be read by a human that isn't code.
      • darig 5 minutes ago
        [dead]
  • hinkley 51 minutes 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 40 minutes 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 36 minutes 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.

  • 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 48 minutes 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 34 minutes 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 29 minutes 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 24 minutes 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.
      • wrs 46 minutes 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 1 hour ago
      Is this AI? Why do we need a summary of the actual article in a comment?
      • bertonvv 1 hour 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 35 minutes ago
          There aren't many commenters at the time you posted this. Which makes this conversation feel even more artificial...
      • WD-42 1 hour ago
        The actual article is AI too so this is just saving you time.
  • dnchdnd 54 minutes ago
    Is valkey the recommended redis alternative these days ?
    • TkTech 32 minutes 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 32 minutes ago
      Yes
  • snissn 1 hour ago
    Do they provide their benchmark code?
  • dropdropteam 1 hour ago
    [flagged]
  • WD-42 1 hour 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.