string case clauses

Discussion in 'Java' started by Roedy Green, Sep 11, 2011.

  1. Roedy Green

    Roedy Green Guest

    Has anyone looked at he code JavaC generates for the new String case
    clauses? It is a simple linear search, a binary search, a HashMap?
    --
    Roedy Green Canadian Mind Products
    http://mindprod.com
    The modern conservative is engaged in one of man's oldest exercises in moral philosophy; that is,
    the search for a superior moral justification for selfishness.
    ~ John Kenneth Galbraith (born: 1908-10-15 died: 2006-04-29 at age: 97)
    Roedy Green, Sep 11, 2011
    #1
    1. Advertising

  2. On 9/11/2011 11:35 AM, Roedy Green wrote:
    > Has anyone looked at he code JavaC generates for the new String case
    > clauses? It is a simple linear search, a binary search, a HashMap?


    <http://blogs.sun.com/darcy/entry/project_coin_string_switch_break>
    discusses the implementation a bit.

    In short:
    1. Switch on the hashcode.
    2. Verify string equalities using a linear switch for all strings that
    have the same hashcode.

    --
    Beware of bugs in the above code; I have only proved it correct, not
    tried it. -- Donald E. Knuth
    Joshua Cranmer, Sep 11, 2011
    #2
    1. Advertising

  3. Roedy Green

    Roedy Green Guest

    On Sun, 11 Sep 2011 12:00:15 -0500, Joshua Cranmer
    <> wrote, quoted or indirectly quoted someone
    who said :

    >1. Switch on the hashcode.
    >2. Verify string equalities using a linear switch for all strings that
    >have the same hashcode.


    ouch. That amounts to a linear search comparing hashcodes. So it is
    not a good idea to replace HashMap lookups with String switches.

    --
    Roedy Green Canadian Mind Products
    http://mindprod.com
    The modern conservative is engaged in one of man's oldest exercises in moral philosophy; that is,
    the search for a superior moral justification for selfishness.
    ~ John Kenneth Galbraith (born: 1908-10-15 died: 2006-04-29 at age: 97)
    Roedy Green, Sep 11, 2011
    #3
  4. Roedy Green

    Arne Vajhøj Guest

    On 9/11/2011 6:33 PM, Roedy Green wrote:
    > On Sun, 11 Sep 2011 12:00:15 -0500, Joshua Cranmer
    > <> wrote, quoted or indirectly quoted someone
    > who said :
    >> 1. Switch on the hashcode.
    >> 2. Verify string equalities using a linear switch for all strings that
    >> have the same hashcode.

    >
    > ouch. That amounts to a linear search comparing hashcodes. So it is
    > not a good idea to replace HashMap lookups with String switches.


    Is anything different from int in pre-1.7?

    Arne
    Arne Vajhøj, Sep 12, 2011
    #4
  5. Roedy Green

    Lew Guest

    Arne Vajhøj wrote:
    > Roedy Green wrote:
    >> Joshua Cranmer wrote, quoted or indirectly quoted someone who said :
    >>> 1. Switch on the hashcode.
    >>> 2. Verify string equalities using a linear switch for all strings that
    >>> have the same hashcode.

    >>
    >> ouch. That amounts to a linear search comparing hashcodes. So it is
    >> not a good idea to replace HashMap lookups with String switches.

    >


    So? How long is your switch statement? Your advice doesn't make sense.

    I thought switches worked by compiled-in jumps to a case label. Was I mistaken? So the only linear search would be on the very rare hash collision, and typically no more than two deep.

    Even if I'm mistaken, a linear search through a handful of cases is not going to take significantly longer than a HashMap lookup, and will avoid the overhead of creating all those objects and concomitant GC pressure. So calmdown your panic, big boy.

    > Is anything different from int in pre-1.7?


    Not really. If your switch is so long that a linear search is a performance problem, you have deeper problems anyway.

    --
    Lew
    Lew, Sep 12, 2011
    #5
  6. Roedy Green

    Arne Vajhøj Guest

    On 9/11/2011 11:54 PM, Lew wrote:
    > Arne Vajhøj wrote:
    >> Roedy Green wrote:
    >>> Joshua Cranmer wrote, quoted or indirectly quoted someone who said :
    >>>> 1. Switch on the hashcode.
    >>>> 2. Verify string equalities using a linear switch for all strings that
    >>>> have the same hashcode.
    >>>
    >>> ouch. That amounts to a linear search comparing hashcodes. So it is
    >>> not a good idea to replace HashMap lookups with String switches.

    >>
    >> Is anything different from int in pre-1.7?

    >
    > Not really.


    And I do not recall anyone complaining about switch on int, so
    yet another non-problem.

    Arne
    Arne Vajhøj, Sep 12, 2011
    #6
  7. Roedy Green

    Roedy Green Guest

    On Sun, 11 Sep 2011 20:05:20 -0700, Peter Duniho
    <> wrote, quoted or indirectly quoted
    someone who said :

    >Huh? How so? It's actually basically the same algorithm a full-on hash
    >table would use. Specifically: hash value gets you to a very small
    >subset of the possible values (very often just one, as long as the hash
    >code algorithm is good), then linear search on collisions.


    Before case strings, there were two JVM instructions for implementing
    an int switch, tableswitch and lookupswitch. The efficient tableswitch
    is a jump table used when the switch values are reasonably dense e.g.
    numbered 0..N. The less efficient lookupswitch is a binary search or
    linear search used when the switch values all over the map.

    I understood the way string case labels worked posted earlier was to
    use the hashCode as the switch variable, which would necessitate the
    use of the inefficient lookupswitch plus a little kludge to deal with
    hashCode collisions.

    In contrast a String case lookup done manually with HashMap does not
    involve any binary search or linear scan. It folds the hashCode to a
    reasonable value and does a table lookup.

    As usual, there is nothing in the JVM spec that says how lookupswitch
    has to be implemented. For maximum speed (but extravagant RAM), the
    JIT could analyse the values, and construct a perfect or near perfect
    hash table. It has the advantage the values are known at load time and
    cannot change. I have seen reference to a number of C algorithms for
    doing this. The JIT has to generate thread-safe code. HashMap does
    not.

    --
    Roedy Green Canadian Mind Products
    http://mindprod.com
    The modern conservative is engaged in one of man's oldest exercises in moral philosophy; that is,
    the search for a superior moral justification for selfishness.
    ~ John Kenneth Galbraith (born: 1908-10-15 died: 2006-04-29 at age: 97)
    Roedy Green, Sep 14, 2011
    #7
  8. Roedy Green

    Lew Guest

    Peter Duniho wrote:
    > Roedy Green wrote:
    >> [...]
    >> I understood the way string case labels worked posted earlier was to
    >> use the hashCode as the switch variable, which would necessitate the
    >> use of the inefficient lookupswitch plus a little kludge to deal with
    >> hashCode collisions.
    >>
    >> In contrast a String case lookup done manually with HashMap does not
    >> involve any binary search or linear scan. It folds the hashCode to a
    >> reasonable value and does a table lookup. [...]

    >
    > I agree with Patricia's assessment. There is no proof that the current
    > implementation of an integral switch would be less efficient than a full
    > hash table implementation, and in fact for relatively few values (as a
    > switch really ought to be), it's likely to be more efficient. At the
    > very least, it's difficult to easily get a small hash table without also
    > having collisions.
    >
    > I see no reason to be concerned whatsoever about the performance
    > implications of the choice of implementation for string case labels in
    > Java. If and when you have a program where that turns out to be a
    > bottleneck, then of course you can look at alternatives. I doubt you'll
    > run into that situation though. And if you do, it's quite likely that
    > you should have been using a hash table structure for other reasons anyway.


    These points or similar were made fairly early in this thread by a couple of people.

    A 'switch' by any other name is still a 'goto'.

    But at least it's forward only.

    --
    Lew
    Lew, Sep 15, 2011
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    15
    Views:
    1,281
    Jerry Coffin
    Feb 1, 2005
  2. Diez B. Roggisch

    for what are for/while else clauses

    Diez B. Roggisch, Nov 14, 2003, in forum: Python
    Replies:
    32
    Views:
    787
    Michele Simionato
    Nov 28, 2003
  3. Fredrik Lundh

    Re: for what are for/while else clauses

    Fredrik Lundh, Nov 18, 2003, in forum: Python
    Replies:
    1
    Views:
    320
    Georgy Pruss
    Nov 18, 2003
  4. Jyotirmoy Bhattacharya

    nested list comprehension and if clauses

    Jyotirmoy Bhattacharya, Jun 28, 2007, in forum: Python
    Replies:
    5
    Views:
    312
    Jyotirmoy Bhattacharya
    Jun 28, 2007
  5. Frank Stutzman
    Replies:
    6
    Views:
    472
    Marc Christiansen
    Nov 20, 2007
Loading...

Share This Page