"Property Numbered" methods: SLOW O(N) INDEXING?

[petermsiegel]

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

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   

[petermsiegel]

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

[Vince|Dyalog]

Hi Pete,

I can reproduce this and have logged this issue as 21418.

Regards,

Vince

[petermsiegel]

As always,
Thank you, Vince.

-Pete