Derby
  1. Derby
  2. DERBY-3882

Expensive cursor name lookup in network server

    Details

    • Type: Improvement Improvement
    • Status: Closed
    • Priority: Minor Minor
    • Resolution: Fixed
    • Affects Version/s: 10.4.2.0
    • Fix Version/s: 10.6.1.0
    • Component/s: Network Server, SQL
    • Labels:
      None
    • Bug behavior facts:
      Performance

      Description

      I have sometimes seen in a profiler that an unreasonably high amount of the CPU time is spent in GenericLanguageConnectionContext.lookupCursorActivation() when the network server is running. That method is used to check that there is no active statement in the current transaction with the same cursor name as the statement currently being executed, and it is normally only used if the executing statement has a cursor name. None of the client-side statements had a cursor name when I saw this.

      The method is always called when the network server executes a statement because the network server assigns a cursor name to each statement even if no cursor name has been set on the client side. If the list of open statements is short, the method is relatively cheap. If one uses ClientConnectionPoolDataSource with the JDBC statement cache, the list of open statements can however be quite long, and lookupCursorActivation() needs to spend a fair amount of time iterating over the list and comparing strings.

      The time spent looking for duplicate names in lookupCursorActivation() is actually wasted time when it is called from the network server, since the network server assigns unique names to the statements it executes, even when there are duplicate names on the client. It would be good if we could reduce the cost of this operation, or perhaps eliminate it completely when the client doesn't use cursor names.

      1. check_hash.diff
        2 kB
        Knut Anders Hatlen
      2. Cursors.java
        1 kB
        Knut Anders Hatlen

        Activity

        Hide
        Knut Anders Hatlen added a comment -

        The network server always sets the cursor name since it doesn't know if the client has set a cursor name or not. If we had a way in DRDA to tell the server that the client has called Statement.setCursorName(), the server didn't have to set the cursor name in the normal case, and the lookup method wouldn't be called. I haven't found any way to set the cursor name in the DRDA spec, but we always have the possibility to define a product-specific code point. Such a solution could also help us getting rid of the where-current-of rewrite in the client driver, which causes bugs like DERBY-1433.

        Show
        Knut Anders Hatlen added a comment - The network server always sets the cursor name since it doesn't know if the client has set a cursor name or not. If we had a way in DRDA to tell the server that the client has called Statement.setCursorName(), the server didn't have to set the cursor name in the normal case, and the lookup method wouldn't be called. I haven't found any way to set the cursor name in the DRDA spec, but we always have the possibility to define a product-specific code point. Such a solution could also help us getting rid of the where-current-of rewrite in the client driver, which causes bugs like DERBY-1433 .
        Hide
        Knut Anders Hatlen added a comment -

        A simple hack that seems to reduce the cost of lookupCursorActivation() to some degree, is to compare the hash codes of the cursor names before we compare the full strings. That is, change "if (cursorName.equals(executingCursorName))" to "if (cursorName.hashCode() == executingCursorName.hashCode() && cursorName.equals(executingCursorName))". The reason why this is cheaper, is that most implementations of the String.hashCode() cache the hash value, so after the warmup it is not necessary to read the contents of the strings, and we only call String.equals() if there is a name collision.

        Show
        Knut Anders Hatlen added a comment - A simple hack that seems to reduce the cost of lookupCursorActivation() to some degree, is to compare the hash codes of the cursor names before we compare the full strings. That is, change "if (cursorName.equals(executingCursorName))" to "if (cursorName.hashCode() == executingCursorName.hashCode() && cursorName.equals(executingCursorName))". The reason why this is cheaper, is that most implementations of the String.hashCode() cache the hash value, so after the warmup it is not necessary to read the contents of the strings, and we only call String.equals() if there is a name collision.
        Hide
        Dag H. Wanvik added a comment - - edited

        > I haven't found any way to set the cursor name in the DRDA spec, but
        > we always have the possibility to define a product-specific code
        > point. Such a solution could also help us getting rid of the
        > where-current-of rewrite in the client driver, which causes bugs like
        > DERBY-1433.

        This seems a good way to evolve this. It seems better to improve the
        communication between the client and the server; this should help
        reduce the need for special hacks on the client. On the downside, the
        client would still need to handle older servers for a while, so it could take
        some time to get rid of the old cruft.

        Show
        Dag H. Wanvik added a comment - - edited > I haven't found any way to set the cursor name in the DRDA spec, but > we always have the possibility to define a product-specific code > point. Such a solution could also help us getting rid of the > where-current-of rewrite in the client driver, which causes bugs like > DERBY-1433 . This seems a good way to evolve this. It seems better to improve the communication between the client and the server; this should help reduce the need for special hacks on the client. On the downside, the client would still need to handle older servers for a while, so it could take some time to get rid of the old cruft.
        Hide
        Knut Anders Hatlen added a comment -

        Here's a patch which implements the simple approach using String.hashCode(). I
        suggest that we go for that approach for now since changing the protocol would
        be a bigger task and riskier. It seems to be sufficient in order to get the
        method off the profiler's list of big CPU consumers in my environment, and we
        can always revisit the issue and change the network protocol later if someone
        has a load where the simple fix is not sufficient.

        The patch makes GenericLanguageConnectionContext.lookupCursorActivation() check
        the hash codes of the two strings before calling String.equals(), and it skips
        equals() if the hash codes are different, as strings with different hash codes
        are never equal. This exploits the fact that the most common implementations of
        java.lang.String cache the hash code, so that computing and comparing the hash
        codes will be reduced to a simple comparison of two integer fields after
        warm-up.

        I've also attached a small test class (Cursor.java) to show the effect of the
        patch. It repeatedly executes "VALUES 1" in an embedded connection with 50 open
        statements, and each statement has a cursor name. "VALUES 1" is executed 2
        million times for warm-up and then 2 million times again with the time being
        recorded. Running the test 10 times with trunk and 10 times with the patch (on
        OpenSolaris, Java version 1.6.0_15), it needed on average ~30% shorter time to
        complete with the patched version. Average/min/max time in seconds for the runs
        is shown below.

        ij> select name, avg(tps) "AVG", min(tps) "MIN", max(tps) "MAX" from results group by name;
        NAME |AVG |MIN |MAX
        --------------------------------------------------
        d3882 |9.0245 |8.515 |9.867
        trunk |12.968401 |11.732 |14.372

        2 rows selected

        All the regression tests ran cleanly with the patch.

        Show
        Knut Anders Hatlen added a comment - Here's a patch which implements the simple approach using String.hashCode(). I suggest that we go for that approach for now since changing the protocol would be a bigger task and riskier. It seems to be sufficient in order to get the method off the profiler's list of big CPU consumers in my environment, and we can always revisit the issue and change the network protocol later if someone has a load where the simple fix is not sufficient. The patch makes GenericLanguageConnectionContext.lookupCursorActivation() check the hash codes of the two strings before calling String.equals(), and it skips equals() if the hash codes are different, as strings with different hash codes are never equal. This exploits the fact that the most common implementations of java.lang.String cache the hash code, so that computing and comparing the hash codes will be reduced to a simple comparison of two integer fields after warm-up. I've also attached a small test class (Cursor.java) to show the effect of the patch. It repeatedly executes "VALUES 1" in an embedded connection with 50 open statements, and each statement has a cursor name. "VALUES 1" is executed 2 million times for warm-up and then 2 million times again with the time being recorded. Running the test 10 times with trunk and 10 times with the patch (on OpenSolaris, Java version 1.6.0_15), it needed on average ~30% shorter time to complete with the patched version. Average/min/max time in seconds for the runs is shown below. ij> select name, avg(tps) "AVG", min(tps) "MIN", max(tps) "MAX" from results group by name; NAME |AVG |MIN |MAX -------------------------------------------------- d3882 |9.0245 |8.515 |9.867 trunk |12.968401 |11.732 |14.372 2 rows selected All the regression tests ran cleanly with the patch.
        Hide
        Bryan Pendleton added a comment -

        > it needed on average ~30% shorter time

        Wow!

        Is this because this particular benchmark has many open named statements
        for the connection? I guess that if the connection has 50 open named statements,
        we call String.equals on average 25 times to find the one we want? Does this
        indicate that we ought to have a hash table here rather than a sequential lookup?

        I'm a bit surprised that String.equals doesn't itself make this optimization. Is this
        worth raising with the JDK itself?

        Your optimization seems reasonable to me, though clearly we don't want to
        go through this complexity for every call to String.equals, just the ones where
        the performance win justifies it.

        Show
        Bryan Pendleton added a comment - > it needed on average ~30% shorter time Wow! Is this because this particular benchmark has many open named statements for the connection? I guess that if the connection has 50 open named statements, we call String.equals on average 25 times to find the one we want? Does this indicate that we ought to have a hash table here rather than a sequential lookup? I'm a bit surprised that String.equals doesn't itself make this optimization. Is this worth raising with the JDK itself? Your optimization seems reasonable to me, though clearly we don't want to go through this complexity for every call to String.equals, just the ones where the performance win justifies it.
        Hide
        Knut Anders Hatlen added a comment -

        I think the reason why it's not used as a general optimization technique for String.equals() is that there are some conditions that must be satisfied before it actually is an optimization:

        1) The same String objects must be compared multiple times, otherwise the cost of calculating the hash codes will be too high compared to the benefit.

        2) There's nothing to gain by comparing the hash codes if the Strings are equal, so it only speeds up the comparisons where we expect a high number of mismatches.

        3) String.equals() is very fast if the strings have different lengths or if the strings differ in one of the first characters, so the optimization has the best effect when comparing strings of the same length with a common prefix.

        The cursor names generated by the network client satisfy all of these conditions. They are on the form SQL_CURLH000C + serial#, which means they are not equal, have a common prefix, and are likely to have the same length. Also, the names are stored in the activation on the server, so they'll be reused and benefit from the caching of the hash code.

        Another reason is, as you mentioned, that a hash table is normally used for such lookups. A hash table could be used in this case as well, but there are some complicating issues that may make it too complex to justify it:

        a) The cursor names are not unique within a connection (open cursors cannot have the same name, but open statements can share the same name as long as they don't have open cursors at the same time). This means that one key (cursor name) can map to many values, so some sort of multi-map must be implemented. In the normal embedded case with no cursor name, all activations will be located in the same bucket (key=null).

        b) A statement can change its cursor name any time. Currently, this is done by simply changing the cursorName field in the activation. If we store the activation list in a hash table, changing the cursor name means that we also need to move the activation from one bucket to another.

        c) There's some code to reclaim memory if the activation list has been big and later shrinks. I'd imagine that this code would be somewhat more complex too if the list is transformed into a multi-map.

        That said, I'm all for replacing the list with a data structure that's more suited for effective lookups. I'd suggest that we go for the current patch proposal for now, since it looks simple and rather harmless, and then revisit the issue and try to come up with a more efficient data structure if this optimization turns out to be insufficient.

        Show
        Knut Anders Hatlen added a comment - I think the reason why it's not used as a general optimization technique for String.equals() is that there are some conditions that must be satisfied before it actually is an optimization: 1) The same String objects must be compared multiple times, otherwise the cost of calculating the hash codes will be too high compared to the benefit. 2) There's nothing to gain by comparing the hash codes if the Strings are equal, so it only speeds up the comparisons where we expect a high number of mismatches. 3) String.equals() is very fast if the strings have different lengths or if the strings differ in one of the first characters, so the optimization has the best effect when comparing strings of the same length with a common prefix. The cursor names generated by the network client satisfy all of these conditions. They are on the form SQL_CURLH000C + serial#, which means they are not equal, have a common prefix, and are likely to have the same length. Also, the names are stored in the activation on the server, so they'll be reused and benefit from the caching of the hash code. Another reason is, as you mentioned, that a hash table is normally used for such lookups. A hash table could be used in this case as well, but there are some complicating issues that may make it too complex to justify it: a) The cursor names are not unique within a connection (open cursors cannot have the same name, but open statements can share the same name as long as they don't have open cursors at the same time). This means that one key (cursor name) can map to many values, so some sort of multi-map must be implemented. In the normal embedded case with no cursor name, all activations will be located in the same bucket (key=null). b) A statement can change its cursor name any time. Currently, this is done by simply changing the cursorName field in the activation. If we store the activation list in a hash table, changing the cursor name means that we also need to move the activation from one bucket to another. c) There's some code to reclaim memory if the activation list has been big and later shrinks. I'd imagine that this code would be somewhat more complex too if the list is transformed into a multi-map. That said, I'm all for replacing the list with a data structure that's more suited for effective lookups. I'd suggest that we go for the current patch proposal for now, since it looks simple and rather harmless, and then revisit the issue and try to come up with a more efficient data structure if this optimization turns out to be insufficient.
        Hide
        Bryan Pendleton added a comment -

        Thanks very much for the thorough and clear explanation; it is quite helpful to understand
        why this optimization works in this case.

        I agree that we should proceed with the current proposal.

        Show
        Bryan Pendleton added a comment - Thanks very much for the thorough and clear explanation; it is quite helpful to understand why this optimization works in this case. I agree that we should proceed with the current proposal.
        Hide
        Knut Anders Hatlen added a comment -

        Committed revision 818807.

        Show
        Knut Anders Hatlen added a comment - Committed revision 818807.

          People

          • Assignee:
            Knut Anders Hatlen
            Reporter:
            Knut Anders Hatlen
          • Votes:
            0 Vote for this issue
            Watchers:
            0 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development