Thanks for all the suggestions so far - I'm investigating them all.

I'm looking for an error of less than 0.001 from the actual average for all buckets (unless the bucket has < 3 or 4 allocations) and the timeframe is less than 3 seconds on a new linux blade.