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

Writing and using Classes in Dyalog APL

### "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
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: 159
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.

petermsiegel

Posts: 159
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
Vince|Dyalog

Posts: 429
Joined: Wed Oct 01, 2008 9:39 am

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

As always,
Thank you, Vince.

-Pete
petermsiegel

Posts: 159
Joined: Thu Nov 11, 2010 11:04 pm