Re: Binary Search
On 03/28/2011 02:02 AM, Wojtek wrote:
Leif Roar Moldskred wrote :
Roedy Green <see_website@mindprod.com.invalid> wrote:
Because it is a hammer for removing fleas. I'm thinking of sets of
less than 20 elements. For small sets, I think you could get better
performance and certainly better RAM usage with something specialised
for small sets.
For that small sets the difference in performance between a custom-made
"BinarySearchableList" and TreeSet will either be insignificant to the
overall program performance or so critical that you'll want to use arrays
instead of lists anyway.
I had a requirement to store over 3K Strings and to retrieve them in a random
fashion. I used a HashSet. One day I had some free time, so I converted the
HashSet to an array, then compared the results.
The array was a faster lookup. In fact I calculated that if the application
ran for a week I could save every week almost a full milli-second compared to
the HashSet.
How could you have accepted such an inefficient algorithm?
Did you account for variations in load, garbage collection, anti-virus
activity, Hotspot optimizations and the like? You know that micro-benchmarks
are notoriously unreliable for general conclusions. For all I know, I could
wind up saving a millisecond a week using HashSet compared to array for my
load profiles.
Don't forget to account for JVM load time!
It occurs to me that the HashSet approach might suffer from infelicitous
coding idioms that interfere with GC. Perhaps you're packratting. (See
<http://mindprod.com/jgloss/packratting.html>.) So what you need to do is
make sure you carefully scope alllll your variables in the HashSet scenario,
and thoroughly instrument your code so you can determine where you're
colliding with the GC. (See <http://mindprod.com/jgloss/profiler.html>.)
You will, of course, need to institute a task force to performance-test your
String-storage module, and to stand up a full suite of JMeter-based tests with
detailed reports to management on whether that millisecond savings is sustainable.
You'll also need contingency strategies, like, what if the program has to
suspend? You'll need to serialize the data and deserialize it later to
resume. Your performance team will need to consider the impact of the choice
of HashSet vs. array for that functionality.
You play this right and that String storage subsystem will merit an entire
department and plenty of big iron with you as lead performance architect. Who
knows? You might want up saving two milliseconds!
--
Lew
Raise your hands - who took all this bullshit seriously? Come on now, admit it!
If you did take it seriously, you don't have what it takes to be a programmer.
Get out now.
I mean it. We don't want you.