[jira] [Commented] (RNG-114) Improve ListSampler shuffle algorithm to detect instances of RandomAccess

["Alex D Herbert (Jira)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/RNG-114?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16925254#comment-16925254 ] 

Alex D Herbert commented on RNG-114:
------------------------------------

I've built a benchmark to investigate the shuffle of a List.

The benchmarking is done using an ArrayList and LinkedList. In the JDK the ArrayList is marked with an interface {{java.util.RandomAccess}} that states that the list supports fast (generally constant time) random access. This allows the JDK to handle lists using appropriate algorithms.

Here is the existing code from ListSampler against {{java.util.Collections.shuffle}}:
||Size||Method||Array||Linked||Relative Array||Relative Linked||
|10|Collections|41.43|92.26| | |
|10|PermutationSampler|67.97|104.04|1.64|1.13|
|100|Collections|437.58|762.51| | |
|100|PermutationSampler|476.92|2152.72|1.09|2.82|
|1000|Collections|4280.79|8275.67| | |
|1000|PermutationSampler|4631.31|331530.26|1.08|40.06|
|10000|Collections|42823.80|112289.16| | |
|10000|PermutationSampler|52537.36|38748538.37|1.23|345.08|

The existing code is a bit slower for ArrayLists and, as expected, the existing code does not handle LinkedList.

The current code in ListSampler creates an array of indices, shuffles them using the PermutationSampler, then uses those indices with a copy of the array to rewrite the original array. In contrast Collections shuffles a RandomAccess list in place, or extracts an array, shuffle that in-place and then rewrites to the original array using a list iterator.

An update of the algorithm has two options:
 # PermutationSamplerRandomAccess: Continue to delegate the shuffle to the PermuationSampler. However detect if the list is RandomAccess and then rewrite to the original array using either direct set of each index or via the list iterator.
 # DirectRandomAccess: Copy the method of Collections and shuffle direct if possible

The method to delegate to PermutationSampler currently duplicates the input List and also creates a list of integers of the same size for a shuffle. In contrast the method of Collections has no memory overhead for DirectAccess lists and only the overhead of a list duplication for non DirectAccess lists.
||Size||Method||Array||Linked||Relative Array||Relative Linked||
|10|Collections|41.43|92.26| | |
|10|DirectRandomAccess|61.99|90.88|1.50|0.99|
|10|PermutationSamplerRandomAccess|67.14|101.13|1.62|1.10|
|100|Collections|437.58|762.51| | |
|100|DirectRandomAccess|406.57|722.86|0.93|0.95|
|100|PermutationSamplerRandomAccess|459.10|703.42|1.05|0.92|
|1000|Collections|4280.79|8275.67| | |
|1000|DirectRandomAccess|4309.85|8322.40|1.01|1.01|
|1000|PermutationSamplerRandomAccess|4849.94|8929.17|1.13|1.08|
|10000|Collections|42823.80|112289.16| | |
|10000|DirectRandomAccess|42645.86|109335.42|1.00|0.97|
|10000|PermutationSamplerRandomAccess|50631.56|113643.49|1.18|1.01|

Here the modification of the original PermutationSampler has removed the quadratic time behaviour for LinkedLists. This method remains a bit slower for ArrayLists.

However these results show that for a full list shuffle using the method from Collections is faster (and is also more memory efficient).
h2. Extension to directional shuffle

The ListSampler also supports a partial shuffle of a list from a start point towards the head or tail of the list. This is where it is appropriate to delegate to the PermutationSampler as the shuffle handles this. The results can be copied back to the original list from the appropriate range that was shuffled.

An update of the algorithm has three options:
 # PermutationSamplerRandomAccess: Continue to delegate the shuffle to the PermuationSampler. However detect if the list is RandomAccess and then rewrite to the original array using either direct set of each index or via the list iterator. The update of the list should detect the range to target in the update (the present method does not do this an updates the entire list).
 # DirectRandomAccessDirectional: Copy the method of Collections and shuffle direct if possible. Modify the shuffle to do a directional shuffle and then update only the target range in the original list.
 # DirectRandomAccessSublist: Exploit the {{List.subList(int, int)}} method to extract a sublist from the input list and then shuffle using the direct method adapted from Collections.

Note for the use of a sublist:
 - ArrayLists return a list that is marked with DirectAccess.
 - LinkedLists that are converted to arrays will only require extra memory for the part of the list that is shuffled.

Here are the results for a shuffle of an array twice. Once from the middle to the head and once from the middle to the tail:
||Size||Method||Array||Linked||Relative Array||Relative Linked||
|10|DirectRandomAccessSublist|46.16|186.48|1.00|1.00|
|10|DirectRandomAccessDirectional|41.99|146.28|0.91|0.78|
|10|PermutationSamplerRandomAccess|105.35|193.64|2.28|1.04|
|100|DirectRandomAccessSublist|500.83|1021.95|1.00|1.00|
|100|DirectRandomAccessDirectional|480.11|1125.24|0.96|1.10|
|100|PermutationSamplerRandomAccess|589.58|1111.30|1.18|1.09|
|1000|DirectRandomAccessSublist|4734.42|10101.32|1.00|1.00|
|1000|DirectRandomAccessDirectional|4676.64|11379.03|0.99|1.13|
|1000|PermutationSamplerRandomAccess|6038.58|13147.48|1.28|1.30|
|10000|DirectRandomAccessSublist|47020.68|155079.67|1.00|1.00|
|10000|DirectRandomAccessDirectional|46537.58|179918.52|0.99|1.16|
|10000|PermutationSamplerRandomAccess|68735.10|171949.83|1.46|1.11|

The relative speed is shown against the sublist method. This overall is the fastest method across the range of array sizes and types. The direct partial shuffle of an ArrayList is faster for small lists. This may be due to the removal of the list iterator which adds an offset to all get and set accessor methods. When the list is larger this effect is less noticeable as speed may be dominated by memory access overhead to the larger array.

These results suggest altering the ListSampler to shuffle using a method similar to the method in Collections. Support for the partial shuffle of lists can be provided using a sublist.
h2. Optimisation

Most of the algorithms in Collections detect DirectAccess lists and switch algorithms. When the non DirectAccess list is small the algorithm for the direct access list is faster than the alternative. For shuffle the LinkedList can use the direct method when the size is less than 5. The Collections source code state that these sizes should be regularly revisited. I have tested lists of size 3-8. The method to shuffle an array in place is faster for lists under size 4:

!LinkedListShufflePerformance.png!

I have uploaded the benchmark and the modified ListSampler to use a shuffle based on Collections in [PR 66|https://github.com/apache/commons-rng/pull/66].

> Improve ListSampler shuffle algorithm to detect instances of RandomAccess
> -------------------------------------------------------------------------
>
>                 Key: RNG-114
>                 URL: https://issues.apache.org/jira/browse/RNG-114
>             Project: Commons RNG
>          Issue Type: Improvement
>          Components: sampling
>    Affects Versions: 1.2
>            Reporter: Alex D Herbert
>            Assignee: Alex D Herbert
>            Priority: Minor
>         Attachments: LinkedListShufflePerformance.png
>
>          Time Spent: 20m
>  Remaining Estimate: 0h
>
> The ListSampler shuffle algorithm uses the input list {{set(index)}} method. If this runs in constant time then the algorithm is fast. If the list is not an instance of {{java.util.RandomAccess}} such as a LinkedList the algorithm will suffer from performance slowdown for large lists.
> This is handled in the JDK Collections.shuffle method by detecting if the list is not an instance of RandomAccess. If so the list {{set(index)}} method is avoided and the list is traversed for update using its iterator.
> Tasks:
>  * Benchmark the ListSampler method verses Collections.shuffle with ArrayList and LinkedList
>  * Update the ListSampler to have comparable performance to Collections.shuffle



--
This message was sent by Atlassian Jira
(v8.3.2#803003)