|
|
Zwiększanie wydajności Set w VisualWorks Smalltalk
Wydajność Set zawierających dużą ilość elementów (> 16000) można znacząco zwiększyć dzięki bardzo prostemu trikowi. Wystarczy zdefiniować podklasę Set, np. BigSet i w tej klasie ponownie zaimplementować metodę klasy Set o nazwie initialIndexFor:boundedBy:.
Metoda ta w klasie Set wygląda następująco:
initialIndexFor: aHashValue boundedBy: length
"Find the place where we should start the search.
Optimize for relatively small dictionaries."
"Objects whose hashes are based on their identityHash are restricted
by current implementations to the range 0 to some small number
like 16383. For collections whose sizes are much larger than this
number, using the hash as-is would tend to cause collisions at the
low end, leading to performance bottlenecks. To compensate, we use
an algorithm to spread small hash values more evenly across large
collections. Large hash values, however, are used as-is, under the
assumption that they are more likely to have been adequately
spread, and also to avoid LargeInteger performance loss."
^(length > SmallCollectionLimit and:
[aHashValue <= ObjectMemory maximumIdentityHashValue])
ifTrue: [aHashValue * (length // SmallCollectionLimit + 1) \\ length + 1]
ifFalse: [aHashValue \\ length + 1]
|
Nowa metoda, którą zdefiniujemy w klasie BigSet wygląda następująco:
initialIndexFor: aHashValue boundedBy: length
"Find the place where we should start the search.
Optimize for big dictionaries (more than 16000 elements)."
^(length > SmallCollectionLimit)
ifTrue: [aHashValue * (length // SmallCollectionLimit + 1) \\ length + 1]
ifFalse: [aHashValue * 5 \\ length + 1]
|
Rozważmy teraz następujący przykład:
aSet := BigSet new. "BigSet zamiast Set"
1 to: 100000 do: [:index | aSet add: index].
|
Szybkość wykonania powyższego kodu jest około 200 (dwieście!) razy większa niż przy użyciu oryginalnego Set.
(jn / pn)
|
