• Jake (unregistered)

    My head just exploded

  • Sam (unregistered)

    Ow. Jesus Christ on a cracker.
    Does he not realize that, at some point, the cost of a larger bytecode offsets any "speed optimizations"?

  • (cs)
  • EE Guy (unregistered) in reply to Jake

    DAMN CS majors!!!

  • (cs) in reply to Sam
    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.
  • A little knowledge is dangerous (unregistered)

    Oh dear

    public void thisCompany throws IdiotOutOnTheirAss

  • EE Guy (unregistered) in reply to Sam
    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?????
  • (cs)

    Anybody want to take a shot at timing this thing?  Is it faster or slower than the regular HashMap?

  • AlbertEin (unregistered)

    I got it!, 5 items are just too few, he must do it with at least 100 items to get the maximum speed!!!!!

  • Michael Suzio (unregistered)

    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.


  • (cs) in reply to loneprogrammer
    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.
  • epslaon (unregistered)

    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.

  • bambino (unregistered)

    He doesn't update size in the clear() method.

  • I must be a geek if I tried this (unregistered) in reply to loneprogrammer
    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

  • bambino (unregistered) in reply to bambino

    Oops!  Didn't notice clear() is a one-way ticket to RealMapLand.

  • Tim Hall (unregistered)

    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.

  • (cs) in reply to WTFer
    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 . . .

  • bhudson (unregistered) in reply to loneprogrammer

    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.

  • (cs)

    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?

  • Tony Morris (unregistered) in reply to Djinn

    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!!

  • billbrasky (unregistered)

    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!


  • (cs) in reply to EE Guy
    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?
  • joe_bruin (unregistered)

    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~!

    <font color="Red"> Something didn't quite work out ...
    - CAPTCHA Validation Incorrect </font>

  • John (unregistered)

    I worked at a company that would have this sort of st 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".




  • (cs) in reply to I must be a geek if I tried this
    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?

  • Anonymous Coward (unregistered)

    In .NET, we have a HybridDictionary for that sort of superstition.  I'm certain that it performs better than that hunk-o'-junk, though.

  • Somebody (unregistered) in reply to bambino

    "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)

  • (cs)

    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.

  • (cs) in reply to EE Guy
    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.
  • Count Spatula (unregistered)

    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.

  • (cs)

    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 =)

  • ByteJuggler (unregistered) in reply to sao

    Sometimes I wonder if some people actually emplouy the techniques for writing unmaintainble code

  • (cs) in reply to EE Guy
    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.
  • (cs)

    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>


  • olddirtybastard (unregistered)

    Glenn? Is that your code?

  • (cs) in reply to jomofo7
    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.<sarcasm></sarcasm>


    True, but likely a non-issue. I think FastMap was mostly created with keys known at compile time.
  • inopia^aardbei (unregistered)

    "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 :)

  • Rolf (unregistered) in reply to inopia^aardbei
    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".
  • (cs)
    <!--StartFragment --><FONT face=Verdana size=2> 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 [:#]</FONT>
  • (cs) in reply to inopia^aardbei
    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?
  • inopia (unregistered) in reply to bullestock

    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.

  • (cs) in reply to inopia
    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.
  • (cs) in reply to John
    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)
  • (cs) in reply to VGR
    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
  • andrey (unregistered) in reply to inopia^aardbei
    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!
  • (cs) in reply to bullestock

    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.

  • (cs) in reply to bambino
    Anonymous:
    He doesn't update size in the clear() method.


    Because there is no need for it. Why to waste CPU cycles?
  • (cs) in reply to ammoQ
    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.
  • (cs) in reply to trollable
    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.

  • UNV (unregistered) in reply to trollable

    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().

Leave a comment on “Pre-mapture Optimization”

Log In or post as a guest

Replying to comment #:

Log Out

« Return to Article