code I wrote myself :)

First one I think of (cause I redid it today, in ruby :) is:

you need to keep a list of lines you already processed in a large log analysis. I'd just use a Set (which is a hash underneath) and get done, although I'd have saved a bunch of overhead (memory allocations, gc pressure) using a bloom filter.

Examples where the "extra overhead" caused an actual problem?

A a few more gigabytes of memory allocated, consequent swapping and slow processing

the one I just wrote you about

What problem did that specific bit of GC pressure cause you? (I'm doing "5 whys" in reverse. Otherwise known as "The Socratic Method.")

sorry I thought I replied yesterday but apparently my comment got lost.

Using a (hash)set instead of a bloom filter caused memory usage to explode, which in turn led to memory thrashing/swapping which in turn led to slow processing times.

The rest of the code runs in constant time (well, linear in the size of the item, with num(items) >> size(items[n]) ) and it did work fine for smaller inputs.

How much slower? Just how much wall clock time did you lose?

hard to estimate I'm sorry. The first naive implementation had been running for more than 15 minutes before I thought it as too much and killed it. Rewrote version run all in about 5.