[GitHub] activemq-artemis pull request #1505: ARTEMIS-1383 Improved Priority queue

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
18 messages Options
Reply | Threaded
Open this post in threaded view
|

[GitHub] activemq-artemis pull request #1505: ARTEMIS-1383 Improved Priority queue

pgfox
GitHub user franz1981 opened a pull request:

    https://github.com/apache/activemq-artemis/pull/1505

    ARTEMIS-1383 Improved Priority queue

    It provides a priority queue implementation that address the typical issues of double linked list ones, while maintaining the performances of the circular buffer based ones.

You can merge this pull request into a Git repository by running:

    $ git pull https://github.com/franz1981/activemq-artemis priority_chunked_q

Alternatively you can review and apply these changes as the patch at:

    https://github.com/apache/activemq-artemis/pull/1505.patch

To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:

    This closes #1505
   
----
commit bbecdf239a90fe96f1b005475afd864cdb765ce7
Author: Francesco Nigro <[hidden email]>
Date:   2017-09-01T22:35:43Z

    ARTEMIS-1383 Improved Priority queue

----


---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at [hidden email] or file a JIRA ticket
with INFRA.
---
Reply | Threaded
Open this post in threaded view
|

[GitHub] activemq-artemis issue #1505: ARTEMIS-1383 Improved Priority queue

pgfox
Github user franz1981 commented on the issue:

    https://github.com/apache/activemq-artemis/pull/1505
 
    @clebertsuconic Please do not merge it, because:
   
    - need to add an additional test on the priority version
    - need to add performance tests to compare it with the linked list one
    - need to configure it better (mabe using the window size?) when used into the core protocol
   
    @tabish121 @gemmellr As far as you know it could be of any use in AMQP too?
   
    Currently, the benchmarks against the latest snapshot show an improvement for the core client of about ~10% more throughput without producing near to 0 garbage under load.
    As soon as I'll provide any JMH benchmark vs the linked list one I'll update this PR.


---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at [hidden email] or file a JIRA ticket
with INFRA.
---
Reply | Threaded
Open this post in threaded view
|

[GitHub] activemq-artemis issue #1505: ARTEMIS-1383 Improved Priority queue

pgfox
In reply to this post by pgfox
Github user clebertsuconic commented on the issue:

    https://github.com/apache/activemq-artemis/pull/1505
 
    What about cases where messages accumulate on bursts and then come close to 0?
   
    A common use case in messaging  is having bursts of production but the consumer takes time to consume but it will eventually get back to 0


---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at [hidden email] or file a JIRA ticket
with INFRA.
---
Reply | Threaded
Open this post in threaded view
|

[GitHub] activemq-artemis issue #1505: ARTEMIS-1383 Improved Priority queue

pgfox
In reply to this post by pgfox
Github user franz1981 commented on the issue:

    https://github.com/apache/activemq-artemis/pull/1505
 
    @clebertsuconic In that case it will shrink, returning to the original size.


---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at [hidden email] or file a JIRA ticket
with INFRA.
---
Reply | Threaded
Open this post in threaded view
|

[GitHub] activemq-artemis issue #1505: ARTEMIS-1383 Improved Priority queue

pgfox
In reply to this post by pgfox
Github user clebertsuconic commented on the issue:

    https://github.com/apache/activemq-artemis/pull/1505
 
    What I'm saying is.  When you measure perf. you have to measure both cases.  Sustained remove and bursts of accumulation.


---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at [hidden email] or file a JIRA ticket
with INFRA.
---
Reply | Threaded
Open this post in threaded view
|

[GitHub] activemq-artemis issue #1505: ARTEMIS-1383 Improved Priority queue

pgfox
In reply to this post by pgfox
Github user franz1981 commented on the issue:

    https://github.com/apache/activemq-artemis/pull/1505
 
    @clebertsuconic Makes sense!
    I've performed both the tests  waiting that they will finish...takes some time!
    I've used the Java Collection LinkedList, Artemis LinkeListImpl, Java Collection ArrayDeque and ChunkedQueue.


---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at [hidden email] or file a JIRA ticket
with INFRA.
---
Reply | Threaded
Open this post in threaded view
|

[GitHub] activemq-artemis issue #1505: ARTEMIS-1383 Improved Priority queue

pgfox
In reply to this post by pgfox
Github user franz1981 commented on the issue:

    https://github.com/apache/activemq-artemis/pull/1505
 
    @clebertsuconic @tabish121 @gemmellr
    I've used JMH to perform the burst tests (ie drainInBurst, pollInBurst) and an unbounded offer/offerFirst (with pure accumulation, to kill any GC, using a huge heap).
   
    ```
    Benchmark                                                              (qType)   Mode  Cnt         Score           Error   Units
   
    --------------------------------------------------------------------------------------------------------------------------------
   
    Burst Size 1024
   
    --------------------------------------------------------------------------------------------------------------------------------
   
    QueueBenchmark.drainInBurst                                       JcLinkedList  thrpt    5     56196.133 ±      9862.363   ops/s
    QueueBenchmark.drainInBurst:·gc.count                             JcLinkedList  thrpt    5         4.000                  counts
    QueueBenchmark.drainInBurst:·gc.time                              JcLinkedList  thrpt    5        17.000                      ms
   
    QueueBenchmark.drainInBurst                                  ArtemisLinkedList  thrpt    5     41398.925 ±     23173.625   ops/s
    QueueBenchmark.drainInBurst:·gc.count                        ArtemisLinkedList  thrpt    5         2.000                  counts
    QueueBenchmark.drainInBurst:·gc.time                         ArtemisLinkedList  thrpt    5         9.000                      ms
   
    QueueBenchmark.drainInBurst                                       ChunkedQueue  thrpt    5    105927.112 ±     37350.450   ops/s
    QueueBenchmark.drainInBurst:·gc.count                             ChunkedQueue  thrpt    5           ≈ 0                  counts
   
    QueueBenchmark.drainInBurst                                         ArrayDeque  thrpt    5    107934.616 ±     32457.204   ops/s
    QueueBenchmark.drainInBurst:·gc.count                               ArrayDeque  thrpt    5           ≈ 0                  counts
   
    --------------------------------------------------------------------------------------------------------------------------------
   
    QueueBenchmark.pollInBurst                                        JcLinkedList  thrpt    5     81885.266 ±     17907.776   ops/s
    QueueBenchmark.pollInBurst:·gc.count                              JcLinkedList  thrpt    5        13.000                  counts
    QueueBenchmark.pollInBurst:·gc.time                               JcLinkedList  thrpt    5        10.000                      ms
   
    QueueBenchmark.pollInBurst                                   ArtemisLinkedList  thrpt    5     63050.521 ±     34661.415   ops/s
    QueueBenchmark.pollInBurst:·gc.count                         ArtemisLinkedList  thrpt    5        18.000                  counts
    QueueBenchmark.pollInBurst:·gc.time                          ArtemisLinkedList  thrpt    5        16.000                      ms
   
    QueueBenchmark.pollInBurst                                        ChunkedQueue  thrpt    5    161280.653 ±     13712.986   ops/s
    QueueBenchmark.pollInBurst:·gc.count                              ChunkedQueue  thrpt    5           ≈ 0                  counts
   
    QueueBenchmark.pollInBurst                                          ArrayDeque  thrpt    5    161606.204 ±     16735.474   ops/s
    QueueBenchmark.pollInBurst:·gc.count                                ArrayDeque  thrpt    5           ≈ 0                  counts
   
    --------------------------------------------------------------------------------------------------------------------------------
   
    QueueBenchmark.offer                                              JcLinkedList  thrpt    5   6546939.112 ±  27962028.115   ops/s
   
    QueueBenchmark.offer                                         ArtemisLinkedList  thrpt    5   7366465.904 ±  31622858.611   ops/s
   
    QueueBenchmark.offer                                              ChunkedQueue  thrpt    5  41271280.062 ± 155829613.478   ops/s
   
    --------------------------------------------------------------------------------------------------------------------------------
   
    QueueBenchmark.offerFirst                                         JcLinkedList  thrpt    5   5911597.446 ±  24163046.423   ops/s
   
    QueueBenchmark.offerFirst                                    ArtemisLinkedList  thrpt    5   3783064.578 ±  23493857.464   ops/s
   
    QueueBenchmark.offerFirst                                         ChunkedQueue  thrpt    5  35790062.086 ± 102802329.954   ops/s
    ```
    As can be seen ChunkedQueue performs for fixed sized bursty scenarios like an ArrayDeque (ie 1 order of magnitude better than any linked list) and for accumulating burst (with no consume involved) one order of magnitude better than a linked list (artemis or the Java Collection one).


---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at [hidden email] or file a JIRA ticket
with INFRA.
---
Reply | Threaded
Open this post in threaded view
|

[GitHub] activemq-artemis issue #1505: ARTEMIS-1383 Improved Priority queue

pgfox
In reply to this post by pgfox
Github user clebertsuconic commented on the issue:

    https://github.com/apache/activemq-artemis/pull/1505
 
    I will wait until the release is complete. I want this backing a little longer before a release. Less risky


---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at [hidden email] or file a JIRA ticket
with INFRA.
---
Reply | Threaded
Open this post in threaded view
|

[GitHub] activemq-artemis issue #1505: ARTEMIS-1383 Improved Priority queue

pgfox
In reply to this post by pgfox
Github user clebertsuconic commented on the issue:

    https://github.com/apache/activemq-artemis/pull/1505
 
    I meant baking :)


---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at [hidden email] or file a JIRA ticket
with INFRA.
---
Reply | Threaded
Open this post in threaded view
|

[GitHub] activemq-artemis issue #1505: ARTEMIS-1383 Improved Priority queue

pgfox
In reply to this post by pgfox
Github user gemmellr commented on the issue:

    https://github.com/apache/activemq-artemis/pull/1505
 
    We use ArrayDeque in the Qpid JMS client, I think thats fine in its client-only context.


---
Reply | Threaded
Open this post in threaded view
|

[GitHub] activemq-artemis issue #1505: ARTEMIS-1383 Improved Priority queue

pgfox
In reply to this post by pgfox
Github user franz1981 commented on the issue:

    https://github.com/apache/activemq-artemis/pull/1505
 
    @gemmellr Yes, ArrayDeque is a top performer, especially with long running constant loads.
    The only downside is that it doubles the size each time is full, so it could create a serious amount of garbage and latencies spikes due to the cost of migrating the elements to the enlarged size.


---
Reply | Threaded
Open this post in threaded view
|

[GitHub] activemq-artemis issue #1505: ARTEMIS-1383 Improved Priority queue

pgfox
In reply to this post by pgfox
Github user gemmellr commented on the issue:

    https://github.com/apache/activemq-artemis/pull/1505
 
    @franz1981 its size is bounded by the amount of oustanding credit the consumer has, so its not going to grow much at all in the client context.


---
Reply | Threaded
Open this post in threaded view
|

[GitHub] activemq-artemis issue #1505: ARTEMIS-1383 Improved Priority queue

pgfox
In reply to this post by pgfox
Github user franz1981 commented on the issue:

    https://github.com/apache/activemq-artemis/pull/1505
 
    @clebertsuconic In the meantime I've done some experiments with [Java Object Layout](http://openjdk.java.net/projects/code-tools/jol/), a tool that compute the deep size of any instance on the heap, to evaluate the difference (memory wise) between `LinkedListImpl` and `ChunkedQueue`.
    I've used a very small chunk size of 32 (ie with arrays of 33 elements for each chunk), to compare with `LinkedListImpl`.
    With no instances:
    ```
    org.apache.activemq.artemis.utils.collections.LinkedListImpl@7ba4f24fd footprint:
         COUNT       AVG       SUM   DESCRIPTION
             1        56        56   [Lorg.apache.activemq.artemis.utils.collections.LinkedListImpl$Iterator;
             1        40        40   org.apache.activemq.artemis.utils.collections.LinkedListImpl
             1        32        32   org.apache.activemq.artemis.utils.collections.LinkedListImpl$Node
             3                 128   (total)
   
   
    org.apache.activemq.load.generator.ChunkedQueue@6ed3ef1d footprint:
         COUNT       AVG       SUM   DESCRIPTION
             1       152       152   [Ljava.lang.Object;
             1        40        40   org.apache.activemq.load.generator.ChunkedQueue
             2                 192   (total)
    ```
    With 31 instances:
    ```
    org.apache.activemq.artemis.utils.collections.LinkedListImpl@7ba4f24fd footprint:
         COUNT       AVG       SUM   DESCRIPTION
             1        56        56   [Lorg.apache.activemq.artemis.utils.collections.LinkedListImpl$Iterator;
             1        24        24   java.lang.Long
             1        40        40   org.apache.activemq.artemis.utils.collections.LinkedListImpl
            32        32      1024   org.apache.activemq.artemis.utils.collections.LinkedListImpl$Node
            35                1144   (total)
   
   
    org.apache.activemq.load.generator.ChunkedQueue@57fa26b7d footprint:
         COUNT       AVG       SUM   DESCRIPTION
             1       152       152   [Ljava.lang.Object;
             1        24        24   java.lang.Long
             1        40        40   org.apache.activemq.load.generator.ChunkedQueue
             3                 216   (total)
    ```
    With 10000 instance:
    ```
    org.apache.activemq.artemis.utils.collections.LinkedListImpl@7ba4f24fd footprint:
         COUNT       AVG       SUM   DESCRIPTION
             1        56        56   [Lorg.apache.activemq.artemis.utils.collections.LinkedListImpl$Iterator;
             1        24        24   java.lang.Long
             1        40        40   org.apache.activemq.artemis.utils.collections.LinkedListImpl
         10001        32    320032   org.apache.activemq.artemis.utils.collections.LinkedListImpl$Node
         10004              320152   (total)
   
   
    org.apache.activemq.load.generator.ChunkedQueue@1894593ad footprint:
         COUNT       AVG       SUM   DESCRIPTION
           323       152     49096   [Ljava.lang.Object;
             1        24        24   java.lang.Long
             1        16        16   java.lang.Object
             1        40        40   org.apache.activemq.load.generator.ChunkedQueue
           326               49176   (total)
    ```
    Totals are pretty explicative, the `ChunkedQueue` (even with very small chunk size) tends to have a 10X smaller memory footprint than a `LinkedListImpl`.
   
   
   



---
Reply | Threaded
Open this post in threaded view
|

[GitHub] activemq-artemis issue #1505: ARTEMIS-1383 Improved Priority queue

pgfox
In reply to this post by pgfox
Github user clebertsuconic commented on the issue:

    https://github.com/apache/activemq-artemis/pull/1505
 
    the biggest chunk you would see in performance would be by changing the QueueImpl's collection.
   
    There are a few requirements we need to meet on that collection. starting from converting PriorityLinkedListTest to work with the same semantics on ChunkedQueue.
   
   
    I don't see an implementation for Iterator at your Queue though.


---
Reply | Threaded
Open this post in threaded view
|

[GitHub] activemq-artemis issue #1505: ARTEMIS-1383 Improved Priority queue

pgfox
In reply to this post by pgfox
Github user franz1981 commented on the issue:

    https://github.com/apache/activemq-artemis/pull/1505
 
    @clebertsuconic Agree, but I wanted to start first with something smaller in order to add features when (if) it proves to be stable enough.
   
    Currently I've provided only a fast (a-la ArrayDeque) internal iterator (ie forEach): an external Iterator is for sure feasible to be implemented using the same algorithm.
    What I've to think better is how implement Iterator::remove and Iterator::repeat operations: I don't know if they can be replaced by something more sympathic with the mechanics of this queue, maybe simplifying the QueueImpl code too.
   
    If it shoudn't be possible I'll try to implement the original semantic of LinkedListImpl's Iterator on ChunkedQueue too, but I really don't know how much time will be needed.


---
Reply | Threaded
Open this post in threaded view
|

[GitHub] activemq-artemis issue #1505: ARTEMIS-1383 Improved Priority queue

pgfox
In reply to this post by pgfox
Github user mtaylor commented on the issue:

    https://github.com/apache/activemq-artemis/pull/1505
 
    @clebertsuconic @franz1981 I see a merge commit, but this PR is still open?


---
Reply | Threaded
Open this post in threaded view
|

[GitHub] activemq-artemis issue #1505: ARTEMIS-1383 Improved Priority queue

pgfox
In reply to this post by pgfox
Github user franz1981 commented on the issue:

    https://github.com/apache/activemq-artemis/pull/1505
 
    @mtaylor @clebertsuconic Right now I can close this without merging anything: I will reopen it after it will be possible to use it as a replacement into the QueueImpl server-side :+1:


---
Reply | Threaded
Open this post in threaded view
|

[GitHub] activemq-artemis pull request #1505: ARTEMIS-1383 Improved Priority queue

pgfox
In reply to this post by pgfox
Github user franz1981 closed the pull request at:

    https://github.com/apache/activemq-artemis/pull/1505


---