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