"Property Numbered" methods: SLOW O(N) INDEXING?
4 posts
• Page 1 of 1
"Property Numbered" methods: SLOW O(N) INDEXING?
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:
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% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
*********************************************************************************
And the source code:
- 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
Last edited by petermsiegel on Sun Jun 02, 2024 3:41 am, edited 4 times in total.
- petermsiegel
- Posts: 160
- Joined: Thu Nov 11, 2010 11:04 pm
Re: Odd Behaviour of "Property Numbered Method" or...
Here's the performance curve (plotting TIME<numbered_method>÷TIME<keyed_method>). Again, accessing a single element of a vector should be O(1), not O(N) or O(logN) with the size N of the array.
https://drive.google.com/file/d/1iagUquJtPEnzrPyXK_jgS5wrHS3DyTU0/view?usp=drive_link
https://drive.google.com/file/d/1iagUquJtPEnzrPyXK_jgS5wrHS3DyTU0/view?usp=drive_link
- petermsiegel
- Posts: 160
- Joined: Thu Nov 11, 2010 11:04 pm
Re: "Property Numbered" methods: SLOW O(N) INDEXING?
Hi Pete,
I can reproduce this and have logged this issue as 21418.
Regards,
Vince
I can reproduce this and have logged this issue as 21418.
Regards,
Vince
- Vince|Dyalog
- Posts: 440
- Joined: Wed Oct 01, 2008 9:39 am
Re: "Property Numbered" methods: SLOW O(N) INDEXING?
As always,
Thank you, Vince.
-Pete
Thank you, Vince.
-Pete
- petermsiegel
- Posts: 160
- Joined: Thu Nov 11, 2010 11:04 pm
4 posts
• Page 1 of 1
Return to Object Oriented Programming
Who is online
Users browsing this forum: No registered users and 1 guest
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group