1INTERNALS(1)          User Contributed Perl Documentation         INTERNALS(1)
2
3
4

NAME

6       PDL::Internals - description of some aspects of the current internals
7

DESCRIPTION

9   Intro
10       This document explains various aspects of the current implementation of
11       PDL. If you just want to use PDL for something, you definitely do not
12       need to read this. Even if you want to interface your C routines to PDL
13       or create new PDL::PP functions, you do not need to read this man page
14       (though it may be informative). This document is primarily intended for
15       people interested in debugging or changing the internals of PDL. To
16       read this, a good understanding of the C language and programming and
17       data structures in general is required, as well as some Perl
18       understanding. If you read through this document and understand all of
19       it and are able to point what any part of this document refers to in
20       the PDL core sources and additionally struggle to understand PDL::PP,
21       you will be awarded the title "PDL Guru" (of course, the current
22       version of this document is so incomplete that this is next to
23       impossible from just these notes).
24
25       Warning: If it seems that this document has gotten out of date, please
26       inform the PDL porters email list (pdl-devel@lists.sourceforge.net).
27       This may well happen.
28
29   ndarrays
30       The pdl data object is generally an opaque scalar reference into a pdl
31       structure in memory. Alternatively, it may be a hash reference with the
32       "PDL" field containing the scalar reference (this makes overloading
33       ndarrays easy, see PDL::Objects). You can easily find out at the Perl
34       level which type of ndarray you are dealing with. The example code
35       below demonstrates how to do it:
36
37          # check if this an ndarray
38          die "not an ndarray" unless UNIVERSAL::isa($pdl, 'PDL');
39          # is it a scalar ref or a hash ref?
40          if (UNIVERSAL::isa($pdl, "HASH")) {
41            die "not a valid PDL" unless exists $pdl->{PDL} &&
42               UNIVERSAL::isa($pdl->{PDL},'PDL');
43            print "This is a hash reference,",
44               " the PDL field contains the scalar ref\n";
45          } else {
46               print "This is a scalar ref that points to address $$pdl in memory\n";
47          }
48
49       The scalar reference points to the numeric address of a C structure of
50       type "pdl" which is defined in pdl.h. The mapping between the object at
51       the Perl level and the C structure containing the actual data and
52       structural that makes up an ndarray is done by the PDL typemap.  The
53       functions used in the PDL typemap are defined pretty much at the top of
54       the file pdlcore.h. So what does the structure look like:
55
56               struct pdl {
57                  unsigned long magicno; /* Always stores PDL_MAGICNO as a sanity check */
58                    /* This is first so most pointer accesses to wrong type are caught */
59                  int state;        /* What's in this pdl */
60
61                  pdl_trans *trans; /* Opaque pointer to internals of transformation from
62                                       parent */
63
64                  pdl_vaffine *vafftrans;
65
66                  void*    sv;      /* (optional) pointer back to original sv.
67                                         ALWAYS check for non-null before use.
68                                         We cannot inc refcnt on this one or we'd
69                                         never get destroyed */
70
71                  void *datasv;        /* Pointer to SV containing data. Refcnt inced */
72                  void *data;            /* Null: no data alloced for this one */
73                  PDL_Indx nvals;           /* How many values allocated */
74                  int datatype;
75                  PDL_Indx   *dims;      /* Array of data dimensions */
76                  PDL_Indx   *dimincs;   /* Array of data default increments */
77                  short    ndims;     /* Number of data dimensions */
78
79                  unsigned char *threadids;  /* Starting index of the thread index set n */
80                  unsigned char nthreadids;
81
82                  pdl_children children;
83
84                  PDL_Indx   def_dims[PDL_NDIMS];   /* Preallocated space for efficiency */
85                  PDL_Indx   def_dimincs[PDL_NDIMS];   /* Preallocated space for efficiency */
86                  unsigned char def_threadids[PDL_NTHREADIDS];
87
88                  struct pdl_magic *magic;
89
90                  void *hdrsv; /* "header", settable from outside */
91               };
92
93       This is quite a structure for just storing some data in - what is going
94       on?
95
96       Data storage
97            We are going to start with some of the simpler members: first of
98            all, there is the member
99
100                    void *datasv;
101
102            which is really a pointer to a Perl SV structure ("SV *"). The SV
103            is expected to be representing a string, in which the data of the
104            ndarray is stored in a tightly packed form. This pointer counts as
105            a reference to the SV so the reference count has been incremented
106            when the "SV *" was placed here (this reference count business has
107            to do with Perl's garbage collection mechanism -- don't worry if
108            this doesn't mean much to you). This pointer is allowed to have
109            the value "NULL" which means that there is no actual Perl SV for
110            this data - for instance, the data might be allocated by a "mmap"
111            operation. Note the use of an SV* was purely for convenience, it
112            allows easy transformation of packed data from files into
113            ndarrays. Other implementations are not excluded.
114
115            The actual pointer to data is stored in the member
116
117                    void *data;
118
119            which contains a pointer to a memory area with space for
120
121                    PDL_Indx nvals;
122
123            data items of the data type of this ndarray.  PDL_Indx is either
124            'long' or 'long long' depending on whether your perl is 64bit or
125            not.
126
127            The data type of the data is stored in the variable
128
129                    int datatype;
130
131            the values for this member are given in the enum "pdl_datatypes"
132            (see pdl.h). Currently we have byte, short, unsigned short, long,
133            index (either long or long long), long long, float and double
134            types, see also PDL::Types.
135
136       Dimensions
137            The number of dimensions in the ndarray is given by the member
138
139                    int ndims;
140
141            which shows how many entries there are in the arrays
142
143                    PDL_Indx   *dims;
144                    PDL_Indx   *dimincs;
145
146            These arrays are intimately related: "dims" gives the sizes of the
147            dimensions and "dimincs" is always calculated by the code
148
149                    PDL_Indx inc = 1;
150                    for(i=0; i<it->ndims; i++) {
151                            it->dimincs[i] = inc; inc *= it->dims[i];
152                    }
153
154            in the routine "pdl_resize_defaultincs" in "pdlapi.c".  What this
155            means is that the dimincs can be used to calculate the offset by
156            code like
157
158                    PDL_Indx offs = 0;
159                    for(i=0; i<it->ndims; i++) {
160                            offs += it->dimincs[i] * index[i];
161                    }
162
163            but this is not always the right thing to do, at least without
164            checking for certain things first.
165
166       Default storage
167            Since the vast majority of ndarrays don't have more than 6
168            dimensions, it is more efficient to have default storage for the
169            dimensions and dimincs inside the PDL struct.
170
171                    PDL_Indx   def_dims[PDL_NDIMS];
172                    PDL_Indx   def_dimincs[PDL_NDIMS];
173
174            The "dims" and "dimincs" may be set to point to the beginning of
175            these arrays if "ndims" is smaller than or equal to the compile-
176            time constant "PDL_NDIMS". This is important to note when freeing
177            an ndarray struct.  The same applies for the threadids:
178
179                    unsigned char def_threadids[PDL_NTHREADIDS];
180
181       Magic
182            It is possible to attach magic to ndarrays, much like Perl's own
183            magic mechanism. If the member pointer
184
185                       struct pdl_magic *magic;
186
187            is nonzero, the PDL has some magic attached to it. The
188            implementation of magic can be gleaned from the file pdlmagic.c in
189            the distribution.
190
191       State
192            One of the first members of the structure is
193
194                    int state;
195
196            The possible flags and their meanings are given in "pdl.h".  These
197            are mainly used to implement the lazy evaluation mechanism and
198            keep track of ndarrays in these operations.
199
200       Transformations and virtual affine transformations
201            As you should already know, ndarrays often carry information about
202            where they come from. For example, the code
203
204                    $y = $x->slice("2:5");
205                    $y .= 1;
206
207            will alter $x. So $y and $x know that they are connected via a
208            "slice"-transformation. This information is stored in the members
209
210                    pdl_trans *trans;
211                    pdl_vaffine *vafftrans;
212
213            Both $x (the parent) and $y (the child) store this information
214            about the transformation in appropriate slots of the "pdl"
215            structure.
216
217            "pdl_trans" and "pdl_vaffine" are structures that we will look at
218            in more detail below.
219
220       The Perl SVs
221            When ndarrays are referred to through Perl SVs, we store an
222            additional reference to it in the member
223
224                    void*    sv;
225
226            in order to be able to return a reference to the user when he
227            wants to inspect the transformation structure on the Perl side.
228
229            Also, we store an opaque
230
231                    void *hdrsv;
232
233            which is just for use by the user to hook up arbitrary data with
234            this sv.  This one is generally manipulated through sethdr and
235            gethdr calls.
236
237   Smart references and transformations: slicing and dicing
238       Smart references and most other fundamental functions operating on
239       ndarrays are implemented via transformations (as mentioned above) which
240       are represented by the type "pdl_trans" in PDL.
241
242       A transformation links input and output ndarrays and contains all the
243       infrastructure that defines how:
244
245       •   output ndarrays are obtained from input ndarrays;
246
247       •   changes in smartly linked output ndarrays (e.g. the child of a
248           sliced parent ndarray) are flown back to the input ndarray in
249           transformations where this is supported (the most often used
250           example being "slice" here);
251
252       •   datatype and size of output ndarrays that need to be created are
253           obtained.
254
255       In general, executing a PDL function on a group of ndarrays results in
256       creation of a transformation of the requested type that links all input
257       and output arguments (at least those that are ndarrays). In PDL
258       functions that support data flow between input and output args (e.g.
259       "slice", "index") this transformation links parent (input) and child
260       (output) ndarrays permanently until either the link is explicitly
261       broken by user request ("sever" at the Perl level) or all parents and
262       children have been destroyed. In those cases the transformation is
263       lazy-evaluated, e.g. only executed when ndarray values are actually
264       accessed.
265
266       In non-flowing functions, for example addition ("+") and inner products
267       ("inner"), the transformation is installed just as in flowing functions
268       but then the transformation is immediately executed and destroyed
269       (breaking the link between input and output args) before the function
270       returns.
271
272       It should be noted that the close link between input and output args of
273       a flowing function (like slice) requires that ndarray objects that are
274       linked in such a way be kept alive beyond the point where they have
275       gone out of scope from the point of view of Perl:
276
277         $x = zeroes(20);
278         $y = $x->slice('2:4');
279         undef $x;    # last reference to $x is now destroyed
280
281       Although $x should now be destroyed according to Perl's rules the
282       underlying "pdl" structure must actually only be freed when $y also
283       goes out of scope (since it still references internally some of $x's
284       data). This example demonstrates that such a dataflow paradigm between
285       PDL objects necessitates a special destruction algorithm that takes the
286       links between ndarrays into account and couples the lifespan of those
287       objects. The non-trivial algorithm is implemented in the function
288       "pdl_destroy" in pdlapi.c. In fact, most of the code in pdlapi.c and
289       pdlfamily.c is concerned with making sure that ndarrays ("pdl *"s) are
290       created, updated and freed at the right times depending on interactions
291       with other ndarrays via PDL transformations (remember, "pdl_trans").
292
293   Accessing children and parents of an ndarray
294       When ndarrays are dynamically linked via transformations as suggested
295       above input and output ndarrays are referred to as parents and
296       children, respectively.
297
298       An example of processing the children of an ndarray is provided by the
299       "baddata" method of PDL::Bad.
300
301       Consider the following situation:
302
303        pdl> $x = rvals(7,7,{Centre=>[3,4]});
304        pdl> $y = $x->slice('2:4,3:5');
305        pdl> ? vars
306        PDL variables in package main::
307
308        Name         Type   Dimension       Flow  State          Mem
309        ----------------------------------------------------------------
310        $x           Double D [7,7]                P            0.38Kb
311        $y           Double D [3,3]                -C           0.00Kb
312
313       Now, if I suddenly decide that $x should be flagged as possibly
314       containing bad values, using
315
316        pdl> $x->badflag(1)
317
318       then I want the state of $y - it's child - to be changed as well (since
319       it will either share or inherit some of $x's data and so be also bad),
320       so that I get a 'B' in the State field:
321
322        pdl> ? vars
323        PDL variables in package main::
324
325        Name         Type   Dimension       Flow  State          Mem
326        ----------------------------------------------------------------
327        $x           Double D [7,7]                PB           0.38Kb
328        $y           Double D [3,3]                -CB          0.00Kb
329
330       This bit of magic is performed by the "propagate_badflag" function,
331       which is listed below:
332
333        /* newval = 1 means set flag, 0 means clear it */
334        /* thanks to Christian Soeller for this */
335
336        void propagate_badflag( pdl *it, int newval ) {
337           PDL_DECL_CHILDLOOP(it)
338           PDL_START_CHILDLOOP(it)
339           {
340               pdl_trans *trans = PDL_CHILDLOOP_THISCHILD(it);
341               int i;
342               for( i = trans->vtable->nparents;
343                    i < trans->vtable->npdls;
344                    i++ ) {
345                   pdl *child = trans->pdls[i];
346
347                   if ( newval ) child->state |=  PDL_BADVAL;
348                   else          child->state &= ~PDL_BADVAL;
349
350                   /* make sure we propagate to grandchildren, etc */
351                   propagate_badflag( child, newval );
352
353               } /* for: i */
354           }
355           PDL_END_CHILDLOOP(it)
356        } /* propagate_badflag */
357
358       Given an ndarray ("pdl *it"), the routine loops through each
359       "pdl_trans" structure, where access to this structure is provided by
360       the "PDL_CHILDLOOP_THISCHILD" macro.  The children of the ndarray are
361       stored in the "pdls" array, after the parents, hence the loop from "i =
362       ...nparents" to "i = ...npdls - 1".  Once we have the pointer to the
363       child ndarray, we can do what we want to it; here we change the value
364       of the "state" variable, but the details are unimportant).  What is
365       important is that we call "propagate_badflag" on this ndarray, to
366       ensure we loop through its children. This recursion ensures we get to
367       all the offspring of a particular ndarray.
368
369       Access to parents is similar, with the "for" loop replaced by:
370
371               for( i = 0;
372                    i < trans->vtable->nparents;
373                    i++ ) {
374                  /* do stuff with parent #i: trans->pdls[i] */
375               }
376
377   What's in a transformation ("pdl_trans")
378       All transformations are implemented as structures
379
380         struct XXX_trans {
381               int magicno; /* to detect memory overwrites */
382               short flags; /* state of the trans */
383               pdl_transvtable *vtable;   /* the all important vtable */
384               void (*freeproc)(struct pdl_trans *);  /* Call to free this trans
385                       (in case we had to malloc some stuff for this trans) */
386               pdl *pdls[NP]; /* The pdls involved in the transformation */
387               int __datatype; /* the type of the transformation */
388               /* in general more members
389               /* depending on the actual transformation (slice, add, etc)
390                */
391         };
392
393       The transformation identifies all "pdl"s involved in the trans
394
395         pdl *pdls[NP];
396
397       with "NP" depending on the number of ndarray args of the particular
398       trans. It records a state
399
400         short flags;
401
402       and the datatype
403
404         int __datatype;
405
406       of the trans (to which all ndarrays must be converted unless they are
407       explicitly typed, PDL functions created with PDL::PP make sure that
408       these conversions are done as necessary). Most important is the pointer
409       to the vtable (virtual table) that contains the actual functionality
410
411        pdl_transvtable *vtable;
412
413       The vtable structure in turn looks something like (slightly simplified
414       from pdl.h for clarity)
415
416         typedef struct pdl_transvtable {
417               pdl_transtype transtype;
418               int flags;
419               int nparents;   /* number of parent pdls (input) */
420               int npdls;      /* number of child pdls (output) */
421               char *per_pdl_flags;  /* optimization flags */
422               void (*redodims)(pdl_trans *tr);  /* figure out dims of children */
423               void (*readdata)(pdl_trans *tr);  /* flow parents to children  */
424               void (*writebackdata)(pdl_trans *tr); /* flow backwards */
425               void (*freetrans)(pdl_trans *tr); /* Free both the contents and it of
426                                               the trans member */
427               pdl_trans *(*copy)(pdl_trans *tr); /* Full copy */
428               int structsize;
429               char *name; /* For debuggers, mostly */
430         } pdl_transvtable;
431
432       We focus on the callback functions:
433
434               void (*redodims)(pdl_trans *tr);
435
436       "redodims" will work out the dimensions of ndarrays that need to be
437       created and is called from within the API function that should be
438       called to ensure that the dimensions of an ndarray are accessible
439       (pdlapi.c):
440
441          void pdl_make_physdims(pdl *it)
442
443       "readdata" and "writebackdata" are responsible for the actual
444       computations of the child data from the parents or parent data from
445       those of the children, respectively (the dataflow aspect).  The PDL
446       core makes sure that these are called as needed when ndarray data is
447       accessed (lazy-evaluation). The general API function to ensure that an
448       ndarray is up-to-date is
449
450         void pdl_make_physvaffine(pdl *it)
451
452       which should be called before accessing ndarray data from XS/C (see
453       Core.xs for some examples).
454
455       "freetrans" frees dynamically allocated memory associated with the
456       trans as needed and "copy" can copy the transformation.  Again,
457       functions built with PDL::PP make sure that copying and freeing via
458       these callbacks happens at the right times. (If they fail to do that we
459       have got a memory leak -- this has happened in the past ;).
460
461       The transformation and vtable code is hardly ever written by hand but
462       rather generated by PDL::PP from concise descriptions.
463
464       Certain types of transformations can be optimized very efficiently
465       obviating the need for explicit "readdata" and "writebackdata" methods.
466       Those transformations are called pdl_vaffine. Most dimension
467       manipulating functions (e.g., "slice", "xchg") belong to this class.
468
469       The basic trick is that parent and child of such a transformation work
470       on the same (shared) block of data which they just choose to interpret
471       differently (by using different "dims", "dimincs" and "offs" on the
472       same data, compare the "pdl" structure above).  Each operation on an
473       ndarray sharing data with another one in this way is therefore
474       automatically flown from child to parent and back -- after all they are
475       reading and writing the same block of memory. This is currently not
476       Perl thread safe -- no big loss since the whole PDL core is not
477       reentrant (Perl threading "!=" PDL threading!).
478
479   Signatures: threading over elementary operations
480       Most of that functionality of PDL threading (automatic iteration of
481       elementary operations over multi-dim ndarrays) is implemented in the
482       file pdlthread.c.
483
484       The PDL::PP generated functions (in particular the "readdata" and
485       "writebackdata" callbacks) use this infrastructure to make sure that
486       the fundamental operation implemented by the trans is performed in
487       agreement with PDL's threading semantics.
488
489   Defining new PDL functions -- Glue code generation
490       Please, see PDL::PP and examples in the PDL distribution.
491       Implementation and syntax are currently far from perfect but it does a
492       good job!
493
494   The Core struct
495       As discussed in PDL::API, PDL uses a pointer to a structure to allow
496       PDL modules access to its core routines. The definition of this
497       structure (the "Core" struct) is in pdlcore.h (created by pdlcore.h.PL
498       in Basic/Core) and looks something like
499
500        /* Structure to hold pointers core PDL routines so as to be used by
501         * many modules
502         */
503        struct Core {
504           I32    Version;
505           pdl*   (*SvPDLV)      ( SV*  );
506           void   (*SetSV_PDL)   ( SV *sv, pdl *it );
507           pdl*   (*pdlnew)      ( );
508           pdl*   (*tmp)         ( );
509           pdl*   (*create)      (int type);
510           void   (*destroy)     (pdl *it);
511           ...
512        }
513        typedef struct Core Core;
514
515       The first field of the structure ("Version") is used to ensure
516       consistency between modules at run time; the following code is placed
517       in the BOOT section of the generated xs code:
518
519        if (PDL->Version != PDL_CORE_VERSION)
520          Perl_croak(aTHX_ "Foo needs to be recompiled against the newly installed PDL");
521
522       If you add a new field to the Core struct you should:
523
524       •    discuss it on the pdl porters email list
525            (pdl-devel@lists.sourceforge.net) [with the possibility of making
526            your changes to a separate branch of the CVS tree if it's a change
527            that will take time to complete]
528
529       •    increase by 1 the value of the $pdl_core_version variable in
530            pdlcore.h.PL. This sets the value of the "PDL_CORE_VERSION" C
531            macro used to populate the Version field
532
533       •    add documentation (e.g. to PDL::API) if it's a "useful" function
534            for external module writers (as well as ensuring the code is as
535            well documented as the rest of PDL ;)
536

BUGS

538       This description is far from perfect. If you need more details or
539       something is still unclear please ask on the pdl-devel mailing list
540       (pdl-devel@lists.sourceforge.net).
541

AUTHOR

543       Copyright(C) 1997 Tuomas J. Lukka (lukka@fas.harvard.edu), 2000 Doug
544       Burke (djburke@cpan.org), 2002 Christian Soeller & Doug Burke, 2013
545       Chris Marshall.
546
547       Redistribution in the same form is allowed but reprinting requires a
548       permission from the author.
549
550
551
552perl v5.34.0                      2021-08-16                      INTERNALS(1)
Impressum