News for hackers. Stuff that matters.
Re:Naggum Nugget by lisper on Tuesday November 02, 2010 @10:44AM (#1860598)
I don't assume anything. I actually did the experiment.
Re:Naggum Nugget by thomas11 on Tuesday November 02, 2010 @11:03AM (#1860668)
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.
Re:Naggum Nugget by StavrosK on Tuesday November 02, 2010 @11:08AM (#1860698)
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).
Re:Naggum Nugget by lisper on Tuesday November 02, 2010 @11:12AM (#1860720)
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.
Re:Naggum Nugget by StavrosK on Tuesday November 02, 2010 @11:21AM (#1860770)
You're certainly not talking about it, so I'll assume you're trolling and leave it at that.
Re:Naggum Nugget by abstractbill on Tuesday November 02, 2010 @02:50PM (#1861767)
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."

Re:Naggum Nugget by lisper on Tuesday November 02, 2010 @08:11PM (#1862995)
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.

Re:Naggum Nugget by StavrosK on Tuesday November 02, 2010 @10:50AM (#1860622)
...and?
Re:Naggum Nugget by lisper on Tuesday November 02, 2010 @11:08AM (#1860689)
And its a lot less than 5000. (And you should do your own homework.)
Re:Naggum Nugget by jimbokun on Tuesday November 02, 2010 @11:31AM (#1860816)
Don't you have a better use of your time than to tell everyone "Hey, I figured this thing out. But I'm not going to tell you the answer."

I'm struggling to think of a non-trolling motivation that explains this behavior.

This is giving me comp.lang.lisp flashbacks.

Re:Naggum Nugget by lisper on Tuesday November 02, 2010 @11:48AM (#1860894)
I was hoping to motivate people to do the experiment for themselves. It's not very hard. Doesn't seem to be working though. Oh well.

On Clozure Common Lisp the breakeven point for the average case is 20 items (10 for the worst case).

Re:Naggum Nugget by StavrosK on Tuesday November 02, 2010 @11:11AM (#1860708)
You did "the experiment"? As in, you compared two specific implementations and came up with a universal point?

Your condescending tone would at least not be completely unwarranted if you weren't utterly wrong.

Re:Naggum Nugget by lisper on Tuesday November 02, 2010 @11:42AM (#1860866)
> you compared two specific implementations

Yes.

> and came up with a universal point

No. I got one data point.

Since there seems to be so much demand for it, I compared ALists and hash tables on Clozure Common Lisp. The breakeven point there was 20 items.