"Property Numbered" methods: SLOW O(N) INDEXING?
Posted: Fri May 24, 2024 11:53 pm
It seems that "Property Numbered" indexing methods (like this: a.GetSlow[1]) in Dyalog run at O(N), depending on the length of the vector being indexed, rather than the expected O(1), even when the index itself is scalar (a single item). "Property Keyed" indexing (like this: a.GetFast[1]) works as expected! Or, ... Did I make a mistake in my formulation? A full test script is run below, followed by the CLASS source code.
The Test Script Output
And the source code: [/size]
The Test Script Output
Code: Select all
]load TestConundrum
#.TestConundrum
TestConundrum.Script
⍝ The conundrum:
⍝ Why (in this example) is a "Property Numbered" method for accessing a single item
⍝ of a vector so slow, compared to its "Property Keyed" equivalent"?
⍝ - More specifically, why does its performance appear to degrade to orders of
⍝ magnitude slower as N (the vector size) increases?
⍝ - As always, this is a gobsmackingly simplified debugging example.
Of course I would never use this method just to access an element of a simple vector.
a←⎕NEW Conundrum 10 ⍝ Accessing a scalar item of VECTOR of length 10
_←a.GetFast[1] → 9.3E¯6 | 0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
_←a.GetSlow[1] → 9.8E¯6 | +5% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
a←⎕NEW Conundrum 1000 ⍝ Accessing a scalar item of VECTOR of length 1000
_←a.GetFast[1] → 9.4E¯6 | 0% ⎕⎕⎕⎕
_←a.GetSlow[1] → 9.2E¯5 | +873% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
a←⎕NEW Conundrum 10000 ⍝ Accessing a scalar item of VECTOR of length 10000
_←a.GetFast[1] → 9.0E¯6 | 0%
_←a.GetSlow[1] → 8.8E¯4 | +9621% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
a←⎕NEW Conundrum 100000 ⍝ Accessing a scalar item of VECTOR of length 100000
_←a.GetFast[1] → 7.8E¯6 | 0%
_←a.GetSlow[1] → 9.1E¯3 | +116150% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
a←⎕NEW Conundrum 1000000 ⍝ Accessing a scalar item of VECTOR of length 1000000
_←a.GetFast[1] → 0.0E0 | 0%
_←a.GetSlow[1] → 9.3E¯2 | +298200% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
*********************************************************************************
Code: Select all
⍝ The Source...
↑⎕SRC TestConundrum
:namespace TestConundrum
⍝ Here's our minimalist class "Conundrum"
⍝ See below for the details...
∇ The_Conundrum
⎕←'⍝ The conundrum:'
⎕←'⍝ Why (in this example) is a "Property Numbered" method for accessing a single item'
⎕←'⍝ of a vector so slow, compared to its "Property Keyed" equivalent"?'
⎕←'⍝ - More specifically, why does its performance appear to be orders of magnitude'
⎕←' slower, worsening as N (the vector size) increases?'
⎕←'⍝ - As always, this is a gobsmackingly simplified debugging example. '
⎕←' Of course I would never use this method just to access an element of a simple vector.'
⎕←''
∇
:class Conundrum
⎕IO←0
:Field Private VECTOR
∇ makeN tally
:Implements constructor
:Access Public
VECTOR← ⍕¨⍳tally
∇
:Property Numbered GetSlow
:Access Public
∇ val← Get args; i
i← args.Indexers
val← VECTOR[i]
∇
∇ r← Shape
r← ⍴VECTOR
∇
:EndProperty
:Property Keyed GetFast
:Access Public
∇ vals← Get args; ii
:If ⎕NULL≡ ii← ⊃args.Indexers
vals← VECTOR
:Else
ii-← (⊃⎕RSI).⎕IO
vals← VECTOR[ii]
:EndIf
∇
:EndProperty
:EndClass
⍝ Here's our test script!!!
∇ Script
;a ;n; test
;⎕IO
;cmpx
⎕IO←0 ⍝ We like 0
{}'cmpx' ⎕CY 'dfns'
The_Conundrum
:FOR n :IN 10 1E3 1E4 1E5 1E6
⍝ Doesn't matter much whether indexing first last or random item...
⎕←''
⎕←'a←⎕NEW Conundrum ',(9↑⍕n),' ⍝ Accessing a scalar item of VECTOR of length',n
a←⎕NEW Conundrum n
test← '_←a.GetFast[1]' '_←a.GetSlow[1]'
⍝ ∊'cmpx',' ',¨test
cmpx test
:EndFor
''
100⍴'*'
'⍝ The Source...'
'↑⎕SRC Conundrum'
↑⎕SRC Conundrum
∇
:endnamespace