help links subscribe changes refresh edit

	SandBox
SandBox Aldor Sieve ←	↑	→ SandBox Boolean

SandBox Arrays

Edit detail for SandBox Arrays revision 1 of 2

	1 2
Editor: page Time: 2007/09/19 18:50:23 GMT-7
Note:

changed:
-
Adding new functions to PrimitiveArray in an attempt to improve
performance.

new(n,x:NNI->S) -- create new array of size n with values from x(i),i=0..n-1

fill!(n,x:NNI->S) -- set the elements of array with values from x(i),i=0..n-1

This is the code for Axiom's PrimitiveArray domain with two small
changes for options to call 'new' and 'fill!' with an initialization
function rather than just a constant.
\begin{spad}
)abbrev domain XPRIMARR XPrimitiveArray
NNI ==> NonNegativeInteger
-- This provides a fast array type with no bound checking on elt's.
-- Minimum index is 0 in this type, cannot be changed
XPrimitiveArray(S:Type): OneDimensionalArrayAggregate S with
     new:(NNI,NNI->S)->%
     fill_!:(%,NNI->S)->%
  == add
   Qmax ==> QVMAXINDEX$Lisp
   Qsize ==> QVSIZE$Lisp
   Qelt ==> ELT$Lisp
   Qsetelt ==> SETELT$Lisp
   Qnew ==> GETREFV$Lisp

   #x                          == Qsize x
   minIndex x                  == 0
   empty()                     == Qnew(0$Lisp)
   new(n:NNI, x:S):%           == fill_!(Qnew n, x)
   new(n:NNI, x:NNI->S):%      == fill_!(Qnew n, x)
   qelt(x, i)                  == Qelt(x, i)
   elt(x:%, i:Integer)         == Qelt(x, i)
   qsetelt_!(x, i, s)          == Qsetelt(x, i, s)
   setelt(x:%, i:Integer, s:S) == Qsetelt(x, i, s)
   fill_!(x:%, s:S):%          == (for i in 0..Qmax x repeat Qsetelt(x, i, s); x)
   fill_!(x:%, s:NNI->S):%     == (for i in 0..Qmax x repeat Qsetelt(x, i, s(i)); x)
\end{spad}

How long does this take?

First, it seems to make a big difference whether the initialization
is done by an anonymous function or by a named function since the
latter can be compiled and called with very little overhead.
In other words using::

  init1(x:Integer):Integer == random(100)-random(100)

is much better than this:
\begin{axiom}
)time on
l0:PRIMARR(INT):=new(100000,0); map!(x+->random(100)-random(100),l0);
\end{axiom}

Old way using a compiled initialization function with the 'map!'
function:
\begin{axiom}
init1(x:Integer):Integer == random(100)-random(100)
l1:PRIMARR(INT):=new(100000,0); map!(init1,l1);
\end{axiom}

New way with the call to the initialization function builtin to
the 'new' function:
\begin{axiom}
init2(x:NNI):Integer == random(100)-random(100)
l2:XPRIMARR(INT):=new(100000,init2);
\end{axiom}
Show the first few entries
\begin{axiom}
for i in 0..10 repeat output [l0.i,l1.i,l2.i]
\end{axiom}

Adding new functions to PrimitiveArray? in an attempt to improve performance.

new(n,x:NNI->S): create new array of size n with values from x(i),i=0..n-1
fill!(n,x:NNI->S): set the elements of array with values from x(i),i=0..n-1

This is the code for Axiom's PrimitiveArray? domain with two small changes for options to call new and fill! with an initialization function rather than just a constant.

spad

)abbrev domain XPRIMARR XPrimitiveArray
NNI ==> NonNegativeInteger
-- This provides a fast array type with no bound checking on elt's.
-- Minimum index is 0 in this type, cannot be changed
XPrimitiveArray(S:Type): OneDimensionalArrayAggregate S with
     new:(NNI,NNI->S)->%
     fill_!:(%,NNI->S)->%
  == add
   Qmax ==> QVMAXINDEX$Lisp
   Qsize ==> QVSIZE$Lisp
   Qelt ==> ELT$Lisp
   Qsetelt ==> SETELT$Lisp
   Qnew ==> GETREFV$Lisp

   #x                          == Qsize x
   minIndex x                  == 0
   empty()                     == Qnew(0$Lisp)
   new(n:NNI, x:S):%           == fill_!(Qnew n, x)
   new(n:NNI, x:NNI->S):%      == fill_!(Qnew n, x)
   qelt(x, i)                  == Qelt(x, i)
   elt(x:%, i:Integer)         == Qelt(x, i)
   qsetelt_!(x, i, s)          == Qsetelt(x, i, s)
   setelt(x:%, i:Integer, s:S) == Qsetelt(x, i, s)
   fill_!(x:%, s:S):%          == (for i in 0..Qmax x repeat Qsetelt(x, i, s); x)
   fill_!(x:%, s:NNI->S):%     == (for i in 0..Qmax x repeat Qsetelt(x, i, s(i)); x)

spad

   Compiling FriCAS source code from file 
      /var/zope2/var/LatexWiki/7193926653459221605-25px001.spad using 
      old system compiler.
   XPRIMARR abbreviates domain XPrimitiveArray 
------------------------------------------------------------------------
   initializing NRLIB XPRIMARR for XPrimitiveArray 
   compiling into NRLIB XPRIMARR 
   processing macro definition Qmax ==> elt(Lisp,QVMAXINDEX) 
   processing macro definition Qsize ==> elt(Lisp,QVSIZE) 
   processing macro definition Qelt ==> elt(Lisp,ELT) 
   processing macro definition Qsetelt ==> elt(Lisp,SETELT) 
   processing macro definition Qnew ==> elt(Lisp,GETREFV) 
   compiling exported # : $ -> NonNegativeInteger
      XPRIMARR;#;$Nni;1 is replaced by QVSIZE 
Time: 0.11 SEC.

   compiling exported minIndex : $ -> Integer
      XPRIMARR;minIndex;$I;2 is replaced by 0 
Time: 0.01 SEC.

   compiling exported empty : () -> $
      XPRIMARR;empty;$;3 is replaced by GETREFV0 
Time: 0 SEC.

   compiling exported new : (NonNegativeInteger,S) -> $
Time: 0.01 SEC.

   compiling exported new : (NonNegativeInteger,NonNegativeInteger -> S) -> $
Time: 0 SEC.

   compiling exported qelt : ($,Integer) -> S
      XPRIMARR;qelt;$IS;6 is replaced by ELT 
Time: 0.01 SEC.

   compiling exported elt : ($,Integer) -> S
      XPRIMARR;elt;$IS;7 is replaced by ELT 
Time: 0 SEC.

   compiling exported qsetelt! : ($,Integer,S) -> S
      XPRIMARR;qsetelt!;$I2S;8 is replaced by SETELT 
Time: 0.01 SEC.

   compiling exported setelt : ($,Integer,S) -> S
      XPRIMARR;setelt;$I2S;9 is replaced by SETELT 
Time: 0 SEC.

   compiling exported fill! : ($,S) -> $
Time: 0.02 SEC.

   compiling exported fill! : ($,NonNegativeInteger -> S) -> $
Time: 0.01 SEC.

****** Domain: S already in scope
augmenting S: (SetCategory)
****** Domain: S already in scope
augmenting S: (OrderedSet)
****** Domain: S already in scope
augmenting S: (Evalable S)
****** Domain: S already in scope
augmenting S: (SetCategory)
****** Domain: S already in scope
augmenting S: (ConvertibleTo (InputForm))
****** Domain: S already in scope
augmenting S: (OrderedSet)
****** Domain: S already in scope
augmenting S: (SetCategory)
(time taken in buildFunctor:  20)

;;;     ***       |XPrimitiveArray| REDEFINED

;;;     ***       |XPrimitiveArray| REDEFINED
Time: 0.31 SEC.

   Cumulative Statistics for Constructor XPrimitiveArray
      Time: 0.49 seconds

   finalizing NRLIB XPRIMARR 
   Processing XPrimitiveArray for Browser database:
--->-->XPrimitiveArray((new (% NNI (Mapping S NNI)))): Not documented!!!!
--->-->XPrimitiveArray((fill! (% % (Mapping S NNI)))): Not documented!!!!
--->-->XPrimitiveArray(constructor): Not documented!!!!
--->-->XPrimitiveArray(): Missing Description
; compiling file "/var/zope2/var/LatexWiki/XPRIMARR.NRLIB/XPRIMARR.lsp" (written 26 MAR 2011 05:16:04 PM):

; /var/zope2/var/LatexWiki/XPRIMARR.NRLIB/XPRIMARR.fasl written
; compilation finished in 0:00:00.211
------------------------------------------------------------------------
   XPrimitiveArray is now explicitly exposed in frame initial 
   XPrimitiveArray will be automatically loaded when needed from 
      /var/zope2/var/LatexWiki/XPRIMARR.NRLIB/XPRIMARR

   >> System error:
   The bounding indices 163 and 162 are bad for a sequence of length 162.
See also:
  The ANSI Standard, Glossary entry for "bounding index designator"
  The ANSI Standard, writeup for Issue SUBSEQ-OUT-OF-BOUNDS:IS-AN-ERROR

How long does this take?

First, it seems to make a big difference whether the initialization is done by an anonymous function or by a named function since the latter can be compiled and called with very little overhead. In other words using:

  init1(x:Integer):Integer == random(100)-random(100)

is much better than this:

axiom

)time on

l0:PRIMARR(INT):=new(100000,0); map!(x+->random(100)-random(100),l0);

Type: PrimitiveArray?(Integer)

axiom

Time: 0.03 (IN) + 0.02 (EV) + 0.03 (OT) = 0.08 sec

Old way using a compiled initialization function with the map! function:

axiom

init1(x:Integer):Integer == random(100)-random(100)

   Function declaration init1 : Integer -> Integer has been added to 
      workspace.

Type: Void

axiom

Time: 0 sec
l1:PRIMARR(INT):=new(100000,0); map!(init1,l1);

axiom

Compiling function init1 with type Integer -> Integer

Type: PrimitiveArray?(Integer)

axiom

Time: 0.03 (EV) + 0.01 (OT) = 0.04 sec

New way with the call to the initialization function builtin to the new function:

axiom

init2(x:NNI):Integer == random(100)-random(100)

   Function declaration init2 : NonNegativeInteger -> Integer has been 
      added to workspace.

Type: Void

axiom

Time: 0.01 (IN) = 0.01 sec
l2:XPRIMARR(INT):=new(100000,init2);

axiom

Compiling function init2 with type NonNegativeInteger -> Integer

Type: XPrimitiveArray?(Integer)

axiom

Time: 0.01 (IN) + 0.01 (EV) + 0.01 (OT) = 0.03 sec

Show the first few entries

axiom

for i in 0..10 repeat output [l0.i,l1.i,l2.i]

   [- 57,36,- 69]
   [- 26,- 14,44]
   [- 53,- 12,21]
   [- 3,- 32,18]
   [30,65,- 34]
   [- 60,43,- 19]
   [- 3,- 11,- 31]
   [11,- 23,26]
   [25,27,12]
   [46,69,50]
   [- 32,- 87,- 41]

Type: Void

axiom

Time: 0.01 (EV) + 0.05 (OT) = 0.06 sec