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

Writing and using Classes in Dyalog APL

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

Postby petermsiegel on 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
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: 153
Joined: Thu Nov 11, 2010 11:04 pm

Re: Odd Behaviour of "Property Numbered Method" or...

Postby petermsiegel on Wed May 29, 2024 6:26 pm

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
petermsiegel
 
Posts: 153
Joined: Thu Nov 11, 2010 11:04 pm

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

Postby Vince|Dyalog on Wed Jun 05, 2024 12:33 pm

Hi Pete,

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

Regards,

Vince
Vince|Dyalog
 
Posts: 420
Joined: Wed Oct 01, 2008 9:39 am

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

Postby petermsiegel on Wed Jun 05, 2024 11:05 pm

As always,
Thank you, Vince.

-Pete
petermsiegel
 
Posts: 153
Joined: Thu Nov 11, 2010 11:04 pm


Return to Object Oriented Programming

Who is online

Users browsing this forum: No registered users and 1 guest