Details

    • Type: Task Task
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: 2.9
    • Fix Version/s: 3.0
    • Component/s: core/other
    • Labels:
      None
    • Lucene Fields:
      New

      Description

      Priority Queue should use generics like all other Java 5 Collection API classes. This very simple, but makes code more readable.

      1. HitQueue.jad
        1 kB
        Uwe Schindler
      2. LUCENE-1935.patch
        12 kB
        Uwe Schindler

        Issue Links

          Activity

          Hide
          Uwe Schindler added a comment - - edited

          Patch for Priority Queue. The usage is not yet generified, but the class itsself is. Now it works like a standard Java 5 Collection (and can for sure be used conventionally).

          (I also removed the tabs/whitespace in the test).

          Show
          Uwe Schindler added a comment - - edited Patch for Priority Queue. The usage is not yet generified, but the class itsself is. Now it works like a standard Java 5 Collection (and can for sure be used conventionally). (I also removed the tabs/whitespace in the test).
          Hide
          Paul Elschot added a comment -

          Uwe, could you take a look at ScorerDocQueue?

          I derived that one from PriorityQueue in 2005 to avoid casts, but now such code duplication may not be necessary anymore.

          In case you think ScorerDocQueue could indeed be removed by using generics instead, I'd gladly try and provide a patch for that.

          Show
          Paul Elschot added a comment - Uwe, could you take a look at ScorerDocQueue? I derived that one from PriorityQueue in 2005 to avoid casts, but now such code duplication may not be necessary anymore. In case you think ScorerDocQueue could indeed be removed by using generics instead, I'd gladly try and provide a patch for that.
          Hide
          Uwe Schindler added a comment - - edited

          Was it to avoid a perforance impact of casting or only for cleaner code? Because the generic version of PQ does noch change anything, the resulting byte code is identical (you can compare that with a decompilation using JAD). The casts are added by the Java Compiler automatically.
          The lessThan method is covariant overloaded (passed through) in subclasses by javac (like in the test): lessThan(Integer, Integer) will appear as such in the class byte code of the subclass, but javac will add lessThan(Object, Object) that delgates to the covariant overload (which may be a small perf impact). It is called by the compiled code of PQ using the (Object, Object) signature (PQ does not know anything about generics in its byte code).

          Show
          Uwe Schindler added a comment - - edited Was it to avoid a perforance impact of casting or only for cleaner code? Because the generic version of PQ does noch change anything, the resulting byte code is identical (you can compare that with a decompilation using JAD). The casts are added by the Java Compiler automatically. The lessThan method is covariant overloaded (passed through) in subclasses by javac (like in the test): lessThan(Integer, Integer) will appear as such in the class byte code of the subclass, but javac will add lessThan(Object, Object) that delgates to the covariant overload (which may be a small perf impact). It is called by the compiled code of PQ using the (Object, Object) signature (PQ does not know anything about generics in its byte code).
          Hide
          Paul Elschot added a comment -

          It was to avoid the performance impact of casting, however I don't remember how big the performance impact was.
          I would hope that nowadays the added casts are optimized away by the JIT.

          Show
          Paul Elschot added a comment - It was to avoid the performance impact of casting, however I don't remember how big the performance impact was. I would hope that nowadays the added casts are optimized away by the JIT.
          Hide
          Uwe Schindler added a comment -

          I think it could be rewritten and the missing functionality with the funny name "topSkipToAndAdjustElsePop" added somewhere. The simpliest would be a subclass:

          public class ScorerDocQueue extends PriorityQueue<HeapedScorerDoc> {...}
          

          I do not know how big the perf impact would be (if there is one). As mentioned before, there is a small oerhead, because the overriden abstract method lessThan(HeapedScorerDoc, HeapedScorerDoc) would be wrapped by javac as lessThan(Object, Object) - a small added cost (do not know how big or jvm optimizes away, which I hope)

          Show
          Uwe Schindler added a comment - I think it could be rewritten and the missing functionality with the funny name "topSkipToAndAdjustElsePop" added somewhere. The simpliest would be a subclass: public class ScorerDocQueue extends PriorityQueue<HeapedScorerDoc> {...} I do not know how big the perf impact would be (if there is one). As mentioned before, there is a small oerhead, because the overriden abstract method lessThan(HeapedScorerDoc, HeapedScorerDoc) would be wrapped by javac as lessThan(Object, Object) - a small added cost (do not know how big or jvm optimizes away, which I hope)
          Hide
          Uwe Schindler added a comment - - edited

          By the way, the covariant overload is optimized away by the compiler (not the JVM), if an anonymous or private (and therefore final) class is used. This is the code from the test:

          private static class IntegerQueue extends PriorityQueue<Integer> {
              public IntegerQueue(int count) {
                  super();
                  initialize(count);
              }
          
              protected boolean lessThan(Integer a, Integer b) {
                  return (a < b);
              }
          }
          

          Is compiled to the following code by Java 1.5 javac:

          private static class TestPriorityQueue$IntegerQueue extends PriorityQueue {
          
              protected boolean lessThan(Object a, Object b) {
                  return ((Integer)a).intValue() < ((Integer)b).intValue();
              }
          
              public TestPriorityQueue$IntegerQueue(int count) {
                  initialize(count);
              }
          }
          

          So normal usage in Lucene would have no impact (would be the same as before). Only if you override a generified PQ with a lessThan method not final or somehow accessible, the compiler has to add the wrapper.

          edit:

          If you want to see, what I mean with "wrapper", look into https://issues.apache.org/jira/secure/attachment/12418140/AttributeSource.jad and there in getAttributeImplIterator(). The inline Iterator overrides next(), but the return type is generic -> compiler adds a "volatile" method (how JAD identifies it).

          Show
          Uwe Schindler added a comment - - edited By the way, the covariant overload is optimized away by the compiler (not the JVM), if an anonymous or private (and therefore final) class is used. This is the code from the test: private static class IntegerQueue extends PriorityQueue< Integer > { public IntegerQueue( int count) { super (); initialize(count); } protected boolean lessThan( Integer a, Integer b) { return (a < b); } } Is compiled to the following code by Java 1.5 javac: private static class TestPriorityQueue$IntegerQueue extends PriorityQueue { protected boolean lessThan( Object a, Object b) { return (( Integer )a).intValue() < (( Integer )b).intValue(); } public TestPriorityQueue$IntegerQueue( int count) { initialize(count); } } So normal usage in Lucene would have no impact (would be the same as before). Only if you override a generified PQ with a lessThan method not final or somehow accessible, the compiler has to add the wrapper. edit: If you want to see, what I mean with "wrapper", look into https://issues.apache.org/jira/secure/attachment/12418140/AttributeSource.jad and there in getAttributeImplIterator(). The inline Iterator overrides next(), but the return type is generic -> compiler adds a "volatile" method (how JAD identifies it).
          Hide
          Mark Miller added a comment - - edited

          Ive tried custom PQ's for use in sorting to avoid the casting not too long ago - I both mirco benched and used a profiler. I didn't see no win. Big fat waste of my time

          edit

          actually non sorting too - tried em both.

          Show
          Mark Miller added a comment - - edited Ive tried custom PQ's for use in sorting to avoid the casting not too long ago - I both mirco benched and used a profiler. I didn't see no win. Big fat waste of my time edit actually non sorting too - tried em both.
          Hide
          Paul Smith added a comment -

          I shall perhaps regret asking this, but is there any reason not to use java.util.PriorityQueue instead? Seems like reinventing the wheel a bit there (I understand historically why Lucene has this class).

          (is Lucene 2.9+ now Java 5, or is that a different discussion altogether?)

          Show
          Paul Smith added a comment - I shall perhaps regret asking this, but is there any reason not to use java.util.PriorityQueue instead? Seems like reinventing the wheel a bit there (I understand historically why Lucene has this class). (is Lucene 2.9+ now Java 5, or is that a different discussion altogether?)
          Hide
          Uwe Schindler added a comment -

          The implementation of Lucene's PriorityQueue is a little bit different and also its API. Would be some work to rewrite the collectors.

          The biggest problem of Java's PQ: It does not let elements fall out when a higher prio entry is inserted and the list is full (no upper limit on list length). The Java list grows like a ArrayList.

          Show
          Uwe Schindler added a comment - The implementation of Lucene's PriorityQueue is a little bit different and also its API. Would be some work to rewrite the collectors. The biggest problem of Java's PQ: It does not let elements fall out when a higher prio entry is inserted and the list is full (no upper limit on list length). The Java list grows like a ArrayList.
          Hide
          Paul Smith added a comment -

          thanks Uwe, I thought I would regret asking, good points there. Shame the JDK doesn't have a fixed size PriorityQueue implementation, that seems a bit of a glaring omission.

          Show
          Paul Smith added a comment - thanks Uwe, I thought I would regret asking, good points there. Shame the JDK doesn't have a fixed size PriorityQueue implementation, that seems a bit of a glaring omission.
          Hide
          Uwe Schindler added a comment - - edited

          Paul Elschot: Do you want to provide a patch for ScorerDocQueue that it subclasses PQ<HeapedScorerDoc>?

          Show
          Uwe Schindler added a comment - - edited Paul Elschot: Do you want to provide a patch for ScorerDocQueue that it subclasses PQ<HeapedScorerDoc>?
          Hide
          Mark Miller added a comment -

          I thought I would regret asking

          Why? Now a bunch of us know a bit more than we did. Information sharing is sweet.

          Show
          Mark Miller added a comment - I thought I would regret asking Why? Now a bunch of us know a bit more than we did. Information sharing is sweet.
          Hide
          Paul Elschot added a comment -

          > Do you want to provide a patch for ScorerDocQueue that it subclasses PQ<HeapedScorerDoc>?

          Yes, however that could also be done at a separate issue.
          Thanks for reminding me of the topSkipToAndAdjustElsePop method.
          At the time the JIT was not able to fully optimize two method calls to a ScorerDocQueue object, so I added that method to the class.

          Btw. ScorerDocQueue is used in disjunction queries when the docs should be scored in order, so it is sensitive to query performance, see LUCENE-365 .

          Show
          Paul Elschot added a comment - > Do you want to provide a patch for ScorerDocQueue that it subclasses PQ<HeapedScorerDoc>? Yes, however that could also be done at a separate issue. Thanks for reminding me of the topSkipToAndAdjustElsePop method. At the time the JIT was not able to fully optimize two method calls to a ScorerDocQueue object, so I added that method to the class. Btw. ScorerDocQueue is used in disjunction queries when the docs should be scored in order, so it is sensitive to query performance, see LUCENE-365 .
          Hide
          Uwe Schindler added a comment -

          Committed revision: 821104

          Show
          Uwe Schindler added a comment - Committed revision: 821104
          Hide
          Uwe Schindler added a comment -

          Hi Paul Elschot: I opened LUCENE-1940 for the refactoring

          Show
          Uwe Schindler added a comment - Hi Paul Elschot: I opened LUCENE-1940 for the refactoring
          Hide
          Uwe Schindler added a comment -

          Just for reference: Here is the generated class (by javac) when overriding lessThan (as example HitQueue), decompiled from the resulting class file by JAD.

          Show
          Uwe Schindler added a comment - Just for reference: Here is the generated class (by javac) when overriding lessThan (as example HitQueue), decompiled from the resulting class file by JAD.

            People

            • Assignee:
              Uwe Schindler
              Reporter:
              Uwe Schindler
            • Votes:
              0 Vote for this issue
              Watchers:
              0 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development