#1259 Set/Bag hasIndex/hasItem at/index removeItem/remove allItems/allIndexes Performance

v4.2.0
open
nobody
None
none
1
2014-09-28
2014-04-20
Erich
No

While timing the performance of several Set methods with the following code, I noticed some issues.

TstSet.rex
/* Test Set~hasIndex/~hasIndex performance */

parse arg N
if N='' then N=100000

call time 'R'
S=.set~new~~putall(.array~new(N)~~fill(0)~allIndexes)
say S~items 'Set items in' time('R') 'sec'

do N; if S~hasIndex(0) then nop; end
say N 'x hasIndex' time('R') 'sec'

do N; if S~hasItem(0) then nop; end
say N 'x hasItem' time('R') 'sec'

do N; if S~at(0)=.nil then nop; end
say N 'x at' time('R') 'sec'

M=N%1000
do M; if S~index(0)=.nil then nop; end
say M 'x index' time('R') 'sec'

do M; S~removeItem(0); end
say M 'x removeItem' time('R') 'sec'

do N; S~remove(0); end
say N 'x remove' time('R') 'sec'

do M; A=S~allItems; end
say M 'x allItems' time('R') 'sec'

do M; A=S~allIndexes; end
say M 'x allIndexes' time('R') 'sec'

While I understand that with [bugs:#1174] "Performance of hasItem on Sets" a fix to forward Set and Bag hasItem messages to hasIndex has been implemented, I'm still seeing hasItem as being significantly slower than hasIndex. Either 10-fold or (under conditions explained below, 700-fold)

The relative performance of the method pairs at/index and removeItem/remove is analogue to what was reported in [bugs:#1174] – maybe a similar fix could be applied here

Surprisingly, the method pair allItems/allIndexes performs equally fast, although I'd have expected them to show the same performance delta as above mentioned pairs

Rather unrelated, a very weird, but completely reproducable timing bug shows up for me, if I compare the cases when above code is called without parameter N (which means the default of 100000 should come into place), or when above code is called with a parameter of 100000: note the "Set items" initialization time changes from 0.295 to 2.631 secs, and the "100000 x hasItem" time goes from 0.137 to 9.73 sec!!

tstset 100000
100000 Set items in 0.295000 sec
100000 x hasIndex 0.016000 sec
100000 x hasItem 0.137000 sec
100000 x at 0.039000 sec
100 x index 0.165000 sec
100 x removeItem 0.131000 sec
100000 x remove 0.016000 sec
100 x allItems 0.409000 sec
100 x allIndexes 0.393000 sec
tstset
100000 Set items in 2.631000 sec
100000 x hasIndex 0.016000 sec
100000 x hasItem 9.730000 sec
100000 x at 0.036000 sec
100 x index 0.137000 sec
100 x removeItem 0.135000 sec
100000 x remove 0.015000 sec
100 x allItems 0.375000 sec
100 x allIndexes 0.386000 sec

Related

Bugs: #1174

Discussion


Anonymous

Cancel  Add attachments





Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:





No, thanks