Comment On Pre-mapture Optimization

Eljay's coworker is afflicted with the rather embarrassing condition of premature optimization. Every few blocks of code, he'll start to panic, worrying that his code isn't fast enough, that he's wasting too many resources, that he's just not doing it perfect. As is often the case, this condition creates some rather entertaining (though often buggy and less efficient) code. The FastMap demonstrates this, employing the superstitious belief that a HashMap with less than five values is just too slow ... [expand full text]
« PrevPage 1 | Page 2Next »

Re: Pre-mapture Optimization

2005-11-23 15:37 • by Jake
My head just exploded

Re: Pre-mapture Optimization

2005-11-23 15:44 • by Sam
Ow. Jesus Christ on a cracker.

Does he not realize that, at some point, the cost of a larger bytecode offsets any "speed optimizations"?

Re: Pre-mapture Optimization

2005-11-23 15:45 • by WTFer

Re: Pre-mapture Optimization

2005-11-23 15:45 • by EE Guy
51675 in reply to 51672
DAMN CS majors!!!

Re: Pre-mapture Optimization

2005-11-23 15:46 • by WTFer
51676 in reply to 51673
Anonymous:
Ow. Jesus Christ on a cracker.

Does he not realize that, at some point, the cost of a larger bytecode offsets any "speed optimizations"?


or the cost of it being unmaintainable or the cost of being just plain ugly.

Re: Pre-mapture Optimization

2005-11-23 15:46 • by A little knowledge is dangerous
Oh dear

public void thisCompany throws IdiotOutOnTheirAss

Re: Pre-mapture Optimization

2005-11-23 15:49 • by EE Guy
51678 in reply to 51673
Anonymous:
Ow. Jesus Christ on a cracker.

Does he not realize that, at some point, the cost of a larger bytecode offsets any "speed optimizations"?




Larger bytecode may/may not be a bad thing...



But the original guy appears to understand little about Hash tables/maps...



A  hash-table would only do 5 string comparisions if there were 4
collisions...  If the table is sparse enough (and the hashing
function good),  collisions would be extremely rare (if at all)...



WTF!! Who PAYS these guys?????

Re: Pre-mapture Optimization

2005-11-23 15:50 • by loneprogrammer
Anybody want to take a shot at timing this thing?  Is it faster or slower than the regular HashMap?

Re: Pre-mapture Optimization

2005-11-23 15:51 • by AlbertEin
I got it!, 5 items are just too few, he must do it with at least 100 items to get the maximum speed!!!!!



Re: Pre-mapture Optimization

2005-11-23 15:52 • by Michael Suzio
Wow, excellent.  Let's create a new, non-standard Map
implementation and then end up 99% of the time just creating a *real*
map underneath that because we couldn't figure out how to implement the
actual Map interface methods ourselves.  If you even put one more value in the object, you're hosed.  Nice.





Re: Pre-mapture Optimization

2005-11-23 15:53 • by WTFer
51682 in reply to 51679
loneprogrammer:
Anybody want to take a shot at timing this
thing?  Is it faster or slower than the regular HashMap?


I think, for all practical purposes, it will only be more idiotic.

Re: Pre-mapture Optimization

2005-11-23 16:00 • by epslaon
I especially like the fact that toString ignores the real HashMap and
always returns the values in the "cached" pairs, and that get and set
always create the real HashMap.

Re: Pre-mapture Optimization

2005-11-23 16:18 • by bambino
He doesn't update size in the clear() method.

Re: Pre-mapture Optimization

2005-11-23 16:20 • by I must be a geek if I tried this
51685 in reply to 51679
loneprogrammer:
Anybody want to take a shot at timing this thing?  Is it faster or slower than the regular HashMap?


I wrote this code:
        for (int ix = 0; ix < 1000000; ix++) {
            FastMap m = new FastMap();
            m.put(String.valueOf(ix), new Integer(ix));
        }

And compared its speed against a HashMap doing the same thing.

As expected, HashMap was faster. Where "FastMap" was faster was this code:

        for (int ix = 0; ix < 1000000; ix++) {

            FastMap m = new FastMap(String.valueOf(ix), new Integer(ix));

        }

Note, I did not attempt actually accessing the data, just looked at it from a .put standpoint

Sadly, I have real work I should be doing


Re: Pre-mapture Optimization

2005-11-23 16:20 • by bambino
51686 in reply to 51684
Oops!  Didn't notice clear() is a one-way ticket to RealMapLand.

Re: Pre-mapture Optimization

2005-11-23 16:27 • by Tim Hall
Well thats the theory behing the .net class HybridDictionary, except it
uses a list for the first 10 and when you add the 11th it switches to a
HashTable, because it is apparently more efficient, of course you would
only use if most of the time the it would contain less than 10, so the
benefits were actually realised, though it doesnt take too much work
for it to swicth to the HashTable.



One major difference is that the HybridDictionary supports the same interface as the HashTable.

Re: Pre-mapture Optimization

2005-11-23 16:28 • by loneprogrammer
51688 in reply to 51682
WTFer:
loneprogrammer:
Anybody want to take a shot at timing this
thing?  Is it faster or slower than the regular HashMap?


I think, for all practical purposes, it will only be more idiotic.


I don't know.  Most purposes can get by with HashMap.



Now that I think about it, this is just an Pair[5] in wolf's
clothing.  The HashMap's initial size is 11 buckets.  So if
you can't spare the memory for 6 Entry objects . . .



Re: Pre-mapture Optimization

2005-11-23 16:30 • by bhudson
51689 in reply to 51679
The one way it might possibly win is that standard-library hashes often
allocate large arrays, so if you have a whole bunch of them, most of
them almost empty, you'd want to do a hack something like this.



But not, of course, in the way this guy is doing things.

Re: Pre-mapture Optimization

2005-11-23 16:31 • by Djinn
I'm actually embarrassed for this guy. If you're out there reading
this: I'm sorry. Very, very sorry your code ended up here, but really:
W-T-F?

Re: Pre-mapture Optimization

2005-11-23 17:21 • by Tony Morris
51691 in reply to 51690
Place Java, data structures, performance and thedailywtf into a boiling pot and stir.

What do you have?

A lethal recipe that is almost certain to invoke the common, yet still amusing, fallacies.

Bring it on!!

Re: Pre-mapture Optimization

2005-11-23 17:21 • by billbrasky
Ugh, what a waste of programming time for questionable speed increases...  I'm glad I'm not paying him to write this garbage.





Oh, and I also like that he made the hash map and his internal methods protected. 
Yeah, like someone will actually extend this garbage.  Hey, wait,
does he know that protected members aren't safe to inline ( 
http://java.sun.com/docs/books/vmspec/2nd-edition/html/Concepts.doc.html#16348
) ?  He might have to go back and optimize a bunch of his code!




Re: Pre-mapture Optimization

2005-11-23 17:32 • by VGR
51693 in reply to 51678
Anonymous:

WTF!! Who PAYS these guys?????




Managers who don't quiz the technical competence of people they hire,
and who cover their ears when told there's an idiot costing them mounds
of money.  Such managers are unfortunately common.



The very first time I have to fix a bug related to that class, you can bet I'll replace its usage with a normal Map.



I once worked with a guy who wrote his own Vector class.  I wish
I'd had the wherewithal then to code up a benchmark of both his class
and a real Vector (or ArrayList).  But these people are typically
so neurotic and bullheaded it probably wouldn't have made even a dent.



By the way, "FastMap" is not a valid implementation of Map. 
Calling map.entrySet().iterator().remove() on a non-empty Map MUST
either remove the corresponding item from the Map, or throw
UnsupportedOperationException.  The same is true of
map.keySet().iterator().remove() and map.values().iterator().remove().



But premature optimizers are already smarter than both the Sun Java
Team and the JCP, so why should they be troubled with reading a class's
contract?

Re: Pre-mapture Optimization

2005-11-23 17:49 • by joe_bruin
I can't believe all of you are missing the SO EXTREMELY OBVIOUS WTF in this code.



Say you have a FastMap.. and you add in four items.  You've
managed to avoid the ever so slow Map.  But now, if you add a
fifth item, OH NO, you have a slow Map!  This code should replace
its use of Map with another FastMap!  If the item you're looking
for is not in your current FastMap, pass the query on to your child
FastMap.  IMAGINE THE SPEED!  It will be a linked list of
FastMaps, clearly the fastest searching and sorting data structure
EVER~!




Something didn't quite work out ...
- CAPTCHA Validation Incorrect


Re: Pre-mapture Optimization

2005-11-23 18:24 • by John
I worked at a company that would have this sort of s**t all over the place. And the comments to code ratio would be the same.



At one point I got into a fairly heated argument with one of the legacy
developers as to why this code wasn't commented as to Why The F**K they
decided to do something like this. The answer was "Code Comments are so
unmaintainable as to be useless, if you are a student of the code, you
should know".









Re: Pre-mapture Optimization

2005-11-23 18:27 • by masklinn
51696 in reply to 51685
Anonymous:
loneprogrammer:
Anybody want to take a shot at timing this thing?  Is it faster or slower than the regular HashMap?


I wrote this code:
        for (int ix = 0; ix < 1000000; ix++) {
            FastMap m = new FastMap();
            m.put(String.valueOf(ix), new Integer(ix));
        }

And compared its speed against a HashMap doing the same thing.

As expected, HashMap was faster. Where "FastMap" was faster was this code:

        for (int ix = 0; ix < 1000000; ix++) {

            FastMap m = new FastMap(String.valueOf(ix), new Integer(ix));

        }

Note, I did not attempt actually accessing the data, just looked at it from a .put standpoint

Sadly, I have real work I should be doing



Have you tried setting the initial size of the HashMap to 4?

Re: Pre-mapture Optimization

2005-11-23 19:02 • by Anonymous Coward
In .NET, we have a HybridDictionary for that sort of
superstition.  I'm certain that it performs better than that
hunk-o'-junk, though.

Re: Pre-mapture Optimization

2005-11-23 19:08 • by Somebody
51698 in reply to 51684
"He doesn't update size in the clear() method."

I missed that when scanning the code, but I noticed that he probably did not mean to do "useHashMap = new HashMap();" there, either.

I also suspect that, if special-casing maps of size 1 through 4 would be more efficient, he should be able to gain more by using if( useMap == null) instead of if( useMap != null). If his compiler does this reasonably, that might improve locality of reference in his bytecodes, and prevent branches in the case where useMap is null (at least if he is using a brain-dead single-pass java compiler)

Re: Pre-mapture Optimization

2005-11-23 19:13 • by trollable
As usual, every one is criticizing but there is maybe good reasons.
Maybe 15% faster for a critical section. Who knows? And the code is
long but perfectly maintainable. I will benchmark it tomorrow for
potential addition.

Re: Pre-mapture Optimization

2005-11-23 19:50 • by frosty
51700 in reply to 51678
Anonymous:


WTF!! Who PAYS these guys?????




He is so caught up in the speed optimization that he is ignoring the
financial optimization (i.e. his pay check).  Maybe he should be
optimized out and 5 guys from India should be contacted to replace
him.  I bet the look on his face when he learns that new-age
optimization would be heartbreaking.



Performance issues should be tracked with programs like JProfiler and
the related.  I recently worked on a problem and that tool was
invaluable.  We found that some 60-80% of our processing time was
going through a lookup function with the comment "Bruteforce..." 
Generally speaking if it doesn't show up on your profiler and you don't
need to optimize the crud out of it, don't optimize it.



P.S. Before a flame war starts, no I am not for outsourcing.  Maybe we should ask the managers who suggest outsourcing if we could outsource their job.

Ouch.

2005-11-23 19:52 • by Count Spatula
This hurt.  I'm not even a Java programmer (perl, here), and I can
see how atrocious this is.  I mean, seriously, I think my IQ just
might have dropped a few points simply from reading this code.

Re: Pre-mapture Optimization

2005-11-23 20:52 • by sao

i do this sorta stuff all the time.


The manager looks and sees a page of code. He looks at me and sees me coding all day long.


Next guy comes in, looks at the code, quits, i have my job back =)

Re: Pre-mapture Optimization

2005-11-23 21:20 • by ByteJuggler
51705 in reply to 51703
Sometimes I wonder if some people actually emplouy the techniques for writing unmaintainble code

Re: Pre-mapture Optimization

2005-11-23 22:34 • by ammoQ
51707 in reply to 51678
EE Guy:


WTF!! Who PAYS these guys?????




I think this is a technically brillant
but overly complicated guy. Those guys are hard to overcome, because
they know the right techno-babble to  convice managers that they
are geniuses.

It takes literally years and several spoiled projects to confirm managers they are the idiots and you are right.

Re: Pre-mapture Optimization

2005-11-23 23:06 • by jomofo7
Here's another WTF, as if there weren't enough already. FastMap allows
you to construct with duplicate keys.  If a method is subsequently called that causes the
internal HashMap to get created, FastMap#get will return different values
before and after the HashMap is initialized.

 

Map m = new FastMap("dupkey", "value1", "dupkey", "value2", "dupkey", "value3", "dupkey", "value4");



assertEquals("value1", (String) m.get("dupkey"));



m.put("anotherkey", "value5");   // causes it to create HashMap and add initial four entries



assertEquals("value1", (String) m.get("dupkey"));  // kablooey, different result: "value4"



<sarcasm>

I suppose the only recourse is to add all my keys to a HashSet before
constructing the FastMap to ensure that I don't add duplicate keys.

</sarcasm>




Re: Pre-mapture Optimization

2005-11-23 23:08 • by olddirtybastard
Glenn? Is that your code?

Re: Pre-mapture Optimization

2005-11-24 00:09 • by ammoQ
51710 in reply to 51708
jomofo7:
Here's another WTF, as if there weren't enough already. FastMap allows
you to construct with duplicate keys.  If a method is subsequently called that causes the
internal HashMap to get created, FastMap#get will return different values
before and after the HashMap is initialized.




True, but likely a non-issue. I think FastMap was mostly created with keys known at compile time.

Re: Pre-mapture Optimization

2005-11-24 02:47 • by inopia^aardbei
"DAMN CS majors!!!"

Well, I'm currently in the process of becoming one, but I can still laugh about that remark :)

Before I started uni I spent a couple of years 'down in the trenches', and I know how the average joe feels about CS majors. The problem for most guys is paycheck envy in combination with the "I'm a better coder than he is" feeling.

Let me clear up a few things. University students do not get trained to write code. At most you get one or two courses of 'object oriented programming' (Java, sometimes C++) and for the rest it's mostly theory and math. University is not really a good place to learn how to code. CS majors that code are is more cases than not really bad at it. Companies that hire CS majors to write code didn't get the point.

A good CS major becomes a consultant, lead engineer or technical advisor and leaves the real programming to the professionals.
A bad CS major cannot get such a job and may take on a programming job instead, usually horrifying colleages with stupidity and incompetence.

just my two cents - let the flamewar begin :)

Re: Pre-mapture Optimization

2005-11-24 03:29 • by Rolf
51713 in reply to 51711
Anonymous:
...
A good CS major becomes a consultant, lead engineer or technical
advisor and leaves the real programming to the professionals.
A bad CS major cannot get such a job and may take on a programming job
instead, usually horrifying colleages with stupidity and incompetence.
just my two cents - let the flamewar begin :)




Yeah, we had both cases in our company. And both are really, really
terrible! Do you want a CS major who didn't write a single line of code
to advise you on how to build your system, let alone estimate how much
it's going to cost to program (and test!) it?  "I don't think so
Tim".

Re: Pre-mapture Optimization

2005-11-24 03:50 • by Joe2015
 This is the most brilliant piece of code ever. Another job well done. And sooo easily extended! Just add the same code  again mechanically (what else was copy-paste invented for?) if you come across the absurd condition of needing more than four name/value pairs. No, that wouldn't ever happen. Your coding is out of style and inefficient if you need more than four.
I thought about creating a FastMapCollection of FastMaps with four entries each to solve that. Hell, that's got to be fast! And saves my job for years because it's a challenge. Whoa, I should become senior software engineer now [:#]

Re: Pre-mapture Optimization

2005-11-24 04:00 • by bullestock
51715 in reply to 51711
Anonymous:
Let me clear up a few things. University
students do not get trained to write code. At most you get one or two
courses of 'object oriented programming' (Java, sometimes C++) and for
the rest it's mostly theory and math. University is not really a good
place to learn how to code.


Correct.

Anonymous:
Companies that hire CS majors to write code didn't get the point.


Where I work we have about 75 % MScEE (such as myself) and 25 % CS
majors. We all do analysis, design, and coding. In our experience it is
hard to find good programmers without a CS or engineering background.

Anonymous:
A good CS major becomes a consultant, lead
engineer or technical advisor and leaves the real programming to the
professionals.


How do you become a "professional" programmer?

Re: Pre-mapture Optimization

2005-11-24 04:23 • by inopia
51717 in reply to 51715
Maybe I should relax my statement a bit so that it applies to the general case. You company seems like a cool place to work :)

Personally I see a difference between design and implementation. I usually compare a software engineer to an architect, and a programmer to a construction worker. Usually an architect doesn't know the first thing about bricklaying or good plumbing, and usually the construction workers don't know anything about the load bearing capacity of a given lintel.

I think the analogy holds when it comes to the complexity of bricklaying, programming is a monkey's job. Designing is an art. I know only few people who are good at both.

Re: Pre-mapture Optimization

2005-11-24 04:28 • by ammoQ
51718 in reply to 51717
Anonymous:
Maybe I should relax my statement a bit so that
it applies to the general case. You company seems like a cool place to
work :) Personally I see a difference between design and
implementation. I usually compare a software engineer to an architect,
and a programmer to a construction worker. Usually an architect doesn't
know the first thing about bricklaying or good plumbing, and usually
the construction workers don't know anything about the load bearing
capacity of a given lintel.
I think the analogy holds when it comes to the complexity of
bricklaying, programming is a monkey's job. Designing is an art. I know
only few people who are good at both.




When programming becomes a monkey jobs, it's time to ask yourself if
you are using the right tools. It's paradox when programmers - who are
supposed to automate repeated tasks - work in a stupidly repeating
routine.

Re: Pre-mapture Optimization

2005-11-24 04:37 • by brazzy
51719 in reply to 51695
Anonymous:


At one point I got into a fairly heated argument with one of the legacy
developers as to why this code wasn't commented as to Why The F**K they
decided to do something like this. The answer was "Code Comments are so
unmaintainable as to be useless, if you are a student of the code, you
should know".





IMO he's partially right. Most comments are useless. People have heard
that commenting is important and write lots of "pro forma" comments
like this:



/**

 * Get the thingamabob.

 *

 * @return the thingamambob

 */

public Object getThingamabob()

{

    // see if it's already been created

    if(tb == null)

    {   // if not, create a new one

        tb = new Thingamabob();

    }

    // Return the thingamabob

    return tb;

}



This junk is totally useless, it adds no information and just obstructs the view of the code, actually decreasing clarity.
Especially because it's all too often wrong (forgot to adjust after
copy-pasting it from somewhere or after the code changes).



People who write crap code also write crap comments that you're actually better off without. Comment-to-code ration is a really bad measure
of quality because it rewards stuff like this and penalizes the
competent coders who use meaningful variable names and comment only
where they are actually useful (i.e. not getters and other obvious
stuff but things like why they are doing something and what a class is for)



Re: Pre-mapture Optimization

2005-11-24 04:42 • by IngramJames
51720 in reply to 51693
VGR:


The very first time I have to fix a bug related to that class, you can bet I'll replace its usage with a normal Map.





Are you sure?  Sometimes replacing code like that reveals a slew
of other bugs.  There could be whole sections of the system which
actually rely on the fact that the code does something really, really
obscure...



I always like to bring cheery news to people :D

Re: Pre-mapture Optimization

2005-11-24 04:43 • by andrey
51721 in reply to 51711
Anonymous:
"DAMN CS majors!!!"
Well, I'm currently in the process of becoming one, but I can still
laugh about that remark :)
Before I started uni I spent a couple of years 'down in the trenches',
and I know how the average joe feels about CS majors. The problem for
most guys is paycheck envy in combination with the "I'm a better coder
than he is" feeling.
Let me clear up a few things. University students do not get trained to
write code. At most you get one or two courses of 'object oriented
programming' (Java, sometimes C++) and for the rest it's mostly theory
and math. University is not really a good place to learn how to code.
CS majors that code are is more cases than not really bad at it.
Companies that hire CS majors to write code didn't get the point.
A good CS major becomes a consultant, lead engineer or technical
advisor and leaves the real programming to the professionals.
A bad CS major cannot get such a job and may take on a programming job
instead, usually horrifying colleages with stupidity and incompetence.
just my two cents - let the flamewar begin :)




Not all CS degrees are made equal.  In the school I'm attending,
most courses have substantial programming components (at least where it
makes sense).  I do take some offense at generalizing CS majors as
bad coders.  A good chunk of posts that appear on this site
contain things that most people wouldn't do after taking CS101.  I
wonder how much time the author of the above masterpiece wasted writing
and debugging it.  What's really sad, the same guy probably would
think nothing of doing a full table select and iterating over the
ResultSet just to get a row count...



Brilliant!

Re: Pre-mapture Optimization

2005-11-24 04:47 • by trollable
51722 in reply to 51715
I have finished to benchmark it (focusing on get()) on Sun JRE 1.5.


FastMap is faster when there is 0, 1 or 2 elements. There is a lot of situations where you would want to use it.



  • 4 elements, Hashmap: 8301136000ms, Fastmap: 8783997000ms, 5.8168062780805%
  • 3 elements, Hashmap: 7533018000ms, Fastmap: 8446358000ms, 12.124489812715167%
  • 2 element, Hashmap: 8153451000ms, Fastmap: 8076644000ms, -0.9420182938488231%
  • 1 element, Hashmap: 5868809000ms, Fastmap: 4958676000ms, -15.50796763022958%
  • 0 element, Hashmap: 5375030000ms, Fastmap: 2771835000ms, -48.43126456968613%



However, I would recommand to have specialized versions: FastMap0, FastMap1, FastMap2.

Re: Pre-mapture Optimization

2005-11-24 04:49 • by trollable
51723 in reply to 51684
Anonymous:
He doesn't update size in the clear() method.




Because there is no need for it. Why to waste CPU cycles?

Re: Pre-mapture Optimization

2005-11-24 04:55 • by brazzy
51724 in reply to 51718
ammoQ:
Anonymous:
I think the analogy holds when it comes to the complexity of
bricklaying, programming is a monkey's job. Designing is an art. I know
only few people who are good at both.




I think the analogy is total crap and the opposite is the case: Only a
good designer can be a competent programmer. The only reason why we
separate the two is that there are usually too few competent people
around and when you force an incompetent guy to program to a
prescribed, good design, there is less opportunity for him to fuck up,
and his fuckups will be easier to correct.



That being said, it's true that there is little correspondence between
CS degree and programming skills, and that is because universities
simply don't teach good programming practices, at least not formally. I
actually don't think anyone does. You're just expected to pick it up as
you go. The reasong why CS grads seems to be worse at it on average is that they can often get hired for their degree, while someone without a degree has to rely on skills and references.



ammoQ:


When programming becomes a monkey jobs, it's time to ask yourself if
you are using the right tools. It's paradox when programmers - who are
supposed to automate repeated tasks - work in a stupidly repeating
routine.




Absolutely. I remember a quote from a guy who worked on one of the
first computers, when programming was basically being "discovered" and
not yet called that. He said that he imagined that there would be "a
fair amount of that kind of work to be done in the future" and that it
should never become tiresome, as everything repetitive could be
automated.

Re: Pre-mapture Optimization

2005-11-24 05:08 • by brazzy
51725 in reply to 51722
trollable:
I have finished to benchmark it (focusing on get()) on Sun JRE 1.5.


FastMap is faster when there is 0, 1 or 2 elements.




Pretty much what I expected. The HashMap apparently does not check the
size for 0 before computing the hash, which for java.lang.String is a
computation that involves all characters  and takes easily twice
as long as a string comparison. Then it has to do at least one actual
string comparison.



But that doesn't change the fact that most of the time the difference is irrelevant especially
when there are so few elements and that FastMap is buggy and needlessly
complicated. Variables with a numerical index in their names are nearly
always a WTF. Using an ArrayList could probably have cut the code size
in half.

Re: Pre-mapture Optimization

2005-11-24 05:15 • by UNV
51726 in reply to 51722

However, I would recommand to have specialized versions: FastMap0, FastMap1, FastMap2.


You'd rather use java.util.Collections.EMPTY_MAP and java.util.Collections.singletonMap().

« PrevPage 1 | Page 2Next »

Add Comment