[Perf] ArrayDeque vs. LinkedList: contre-exemple
Bonjour,
Je développe une librairie Java dont le coeur repose sur une queue.
En me fiant à la Javadoc, j'ai donc choisit comme implémentation de bases, une ArrayDeque, et j'ai rédigé un petit stress test censé éprouvé la structure.
J'ai ensuite comparé les résultats du test avec ceux du même test où la queue est une LinkedList. Et contre toutes attentes, la linkedlist est plus performante.
En profilant un peu, je me rend compte que le GC n'est pas appelé avec l'ArrayDeque, alors qu'il l'est avec la LinkedList. Je décide alors de réduire la mémoire allouée (-Xmx512m -Xms512m => -Xmx32m -Xms32m), et l'ArrayDeque redevient compétitive (le GC est alors appelé une fois).
Je n'ai pas réussi à extraire un test unitaire simplifié pour montrer le cas en quelques lignes, mais voici les traces des executions:
"-Xmx512m -Xms512m -verbose:gc" + ArrayDeque
"-Xmx512m -Xms512m -verbose:gc" + LinkedList
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
[GC 34112K->4787K(520064K), 0.0240141 secs]
[GC 38899K->6535K(520064K), 0.0272323 secs]
[GC 40647K->5631K(520064K), 0.0011269 secs]
[GC 39743K->4964K(520064K), 0.0013474 secs]
[GC 39076K->4753K(520064K), 0.0007446 secs]
[GC 38865K->4800K(520064K), 0.0015623 secs]
[GC 38912K->4781K(520064K), 0.0004258 secs]
[GC 38893K->4827K(520064K), 0.0016454 secs]
[GC 38939K->4799K(520064K), 0.0004997 secs]
[GC 38911K->4747K(520064K), 0.0016101 secs]
[GC 38859K->4804K(520064K), 0.0005754 secs]
[GC 38916K->4779K(520064K), 0.0012793 secs]
[GC 38891K->4828K(520064K), 0.0017775 secs]
[GC 38940K->4801K(520064K), 0.0061761 secs]
[GC 38913K->4747K(520064K), 0.0007092 secs]
[GC 38859K->4806K(520064K), 0.0016287 secs]
[GC 38918K->4748K(520064K), 0.0006574 secs]
[GC 38860K->4836K(520064K), 0.0015062 secs]
Total 3,324s |
"-Xmx32m -Xms32m -verbose:gc" + ArrayDeque
Code:
1
2
3
|
[GC 17024K->3521K(30656K), 0.0261077 secs]
Total 3,072s |
Certains d'entre vous ont-ils des pistes pour m'aider à résoudre ce problème sans avoir à jouer avec les paramètres de la JVM?
C'est assez étonnant que le GC aide autant la résolution du problème (je précise que le pb est résolu de manière déterministe, et, mis à part celles propres aux structures de queues, les opérations exécutées sont strictement les mêmes dans les 3 cas).
Charles
