7 ms·

You did the experiment for one particular problem, with two particular implementations, on particular hardware. That doesn't mean you've discovered a universall

You did the experiment for one particular problem, with two particular implementations, on particular hardware. That doesn't mean you've discovered a universally valid break-even point.

StavrosK 16y ago
I assume that's obvious, so lisper must mean something else. Regardless, if you know your complexities it's trivial to find the break-even point with math (list complexity = hash complexity, solve for n).
lisper 16y ago
I don't see how you could possibly know what I did and didn't do. And I never claimed to have discovered a universally valid break-even point.
- StavrosK 16y ago
  You're certainly not talking about it, so I'll assume you're trolling and leave it at that.
- abstractbill 16y ago
  I never claimed to have discovered a universally valid break-even point. The confusion stems from the language you used in your comment, which made it seem like you were claiming a lot more than you actually turned out to be: "I have yet to see anyone ... actually do the experiment to determine where the actual breakeven point is. Hint: it's less than 5000."
  - lisper 16y ago
    Performance break-even is always with respect to a particular implementation. And even with only a single data point I could state (and still can) with very high confidence that no matter what implementation you run your test on, the break-even point will be less than 5000. A LOT less. You'd have to go out of your way to find a hash table implementation so bad that the break-even point was even within an order of magnitude of 5000. Even just reasoning from first principles you could reasonably guess that the break-even would be a lot less than 5000. Traversing a 5000-element AList requires 5000 memory accesses, with no guarantees of locality of reference so you're probably blowing out your cache dozens (thousands if you're unlucky) of times. You probably couldn't write a hash table implementation whose performance was that bad if you tried. The fact of the matter is that hash tables are faster than ALists in all but the most trivial of cases. Theory predicts it, and an experiment that takes all of two minutes to do confirms it. Everything else is quibbling over angels on the head of a pin.

You did the experiment for one particular problem, with two particular implementations, on particular hardware. That doesn't mean you've discovered a universally valid break-even point.

StavrosK 16y ago

I assume that's obvious, so lisper must mean something else. Regardless, if you know your complexities it's trivial to find the break-even point with math (list complexity = hash complexity, solve for n).

lisper 16y ago

I don't see how you could possibly know what I did and didn't do. And I never claimed to have discovered a universally valid break-even point.

StavrosK 16y ago
You're certainly not talking about it, so I'll assume you're trolling and leave it at that.
abstractbill 16y ago
I never claimed to have discovered a universally valid break-even point. The confusion stems from the language you used in your comment, which made it seem like you were claiming a lot more than you actually turned out to be: "I have yet to see anyone ... actually do the experiment to determine where the actual breakeven point is. Hint: it's less than 5000."
- lisper 16y ago
  Performance break-even is always with respect to a particular implementation. And even with only a single data point I could state (and still can) with very high confidence that no matter what implementation you run your test on, the break-even point will be less than 5000. A LOT less. You'd have to go out of your way to find a hash table implementation so bad that the break-even point was even within an order of magnitude of 5000. Even just reasoning from first principles you could reasonably guess that the break-even would be a lot less than 5000. Traversing a 5000-element AList requires 5000 memory accesses, with no guarantees of locality of reference so you're probably blowing out your cache dozens (thousands if you're unlucky) of times. You probably couldn't write a hash table implementation whose performance was that bad if you tried. The fact of the matter is that hash tables are faster than ALists in all but the most trivial of cases. Theory predicts it, and an experiment that takes all of two minutes to do confirms it. Everything else is quibbling over angels on the head of a pin.