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 PDL_Value value; /* to store at least one value */
100 };
101 This is quite a structure for just storing some data in - what is going
103 on?
104 Data storage
106 We are going to start with some of the simpler members: first of all,
108 there are the members (as of 2.078)
109 void *datasv;
111 PDL_Value value; /* to store at least one value */
112 which are a pointer to a Perl SV structure ("SV *"), and a union value
114 of all possible single PDL values. If the ndarray's whole data will fit
115 in the "value", the "datasv" will not be used except by "get_dataref"
116 in PDL::Core for temporary use by Perl code. It will then be destroyed
117 by the call to "upd_data" in PDL::Core method unless that is passed a
118 true value to keep the "datasv" around (largely used by the memory-
119 mapping implementation).
120 Otherwise, the SV is expected to be representing a string, in which the
122 data of the ndarray is stored in a tightly packed form. This pointer
123 counts as a reference to the SV so the reference count has been
124 incremented when the "SV *" was placed here (this reference count
125 business has to do with Perl's garbage collection mechanism -- don't
126 worry if this doesn't mean much to you). This pointer is allowed to
127 have the value "NULL" which means that there is no actual Perl SV for
128 this data, as alluded above. Note the use of an SV* was purely for
129 convenience, it allows easy transformation of packed data from files
130 into ndarrays. Other implementations are not excluded.
131 The actual pointer to data is stored in the member
133 void *data;
135 which contains a pointer to a memory area with space for
137 PDL_Indx nvals;
139 data items of the data type of this ndarray. PDL_Indx is either 'long'
141 or 'long long' depending on whether your perl is 64bit or not.
142 The data type of the data is stored in the variable
144 int datatype;
146 the values for this member are given in the enum "pdl_datatypes" (see
148 pdl.h). Currently we have byte, short, unsigned short, long, index
149 (either long or long long), long long, float and double (plus complex
150 equivalents) types, see also PDL::Types.
151 Dimensions
153 The number of dimensions in the ndarray is given by the member
155 int ndims;
157 which shows how many entries there are in the arrays
159 PDL_Indx *dims;
161 PDL_Indx *dimincs;
162 These arrays are intimately related: "dims" gives the sizes of the
164 dimensions and "dimincs" is always calculated by the code
165 PDL_Indx inc = 1;
167 for(i=0; i<it->ndims; i++) {
168 it->dimincs[i] = inc; inc *= it->dims[i];
169 }
170 in the routine "pdl_resize_defaultincs" in "pdlapi.c". What this means
172 is that the dimincs can be used to calculate the offset by code like
173 PDL_Indx offs = 0;
175 for(i=0; i<it->ndims; i++) {
176 offs += it->dimincs[i] * index[i];
177 }
178 but this is not always the right thing to do, at least without checking
180 for certain things first.
181 Default storage
183 Since the vast majority of ndarrays don't have more than 6 dimensions,
185 it is more efficient to have default storage for the dimensions and
186 dimincs inside the PDL struct.
187 PDL_Indx def_dims[PDL_NDIMS];
189 PDL_Indx def_dimincs[PDL_NDIMS];
190 The "dims" and "dimincs" may be set to point to the beginning of these
192 arrays if "ndims" is smaller than or equal to the compile-time constant
193 "PDL_NDIMS". This is important to note when freeing an ndarray struct.
194 The same applies for the broadcastids:
195 unsigned char def_broadcastids[PDL_NBROADCASTIDS];
197 Magic
199 It is possible to attach magic to ndarrays, much like Perl's own magic
201 mechanism. If the member pointer
202 struct pdl_magic *magic;
204 is nonzero, the PDL has some magic attached to it. The implementation
206 of magic can be gleaned from the file pdlmagic.c in the distribution.
207 State
209 One of the first members of the structure is
211 int state;
213 The possible flags and their meanings are given in "pdl.h". These are
215 mainly used to implement the lazy evaluation mechanism and keep track
216 of ndarrays in these operations.
217 Transformations and virtual affine transformations
219 As you should already know, ndarrays often carry information about
221 where they come from. For example, the code
222 $y = $x->slice("2:5");
224 $y .= 1;
225 will alter $x. So $y and $x know that they are connected via a
227 "slice"-transformation. This information is stored in the members
228 pdl_trans *trans_parent;
230 pdl_vaffine *vafftrans;
231 Both $x (the parent) and $y (the child) store this information about
233 the transformation in appropriate slots of the "pdl" structure.
234 "pdl_trans" and "pdl_vaffine" are structures that we will look at in
236 more detail below.
237 The Perl SVs
239 When ndarrays are referred to through Perl SVs, we store an additional
241 reference to it in the member
242 void* sv;
244 in order to be able to return a reference to the user when they want to
246 inspect the transformation structure on the Perl side.
247 Also, we store an opaque
249 void *hdrsv;
251 which is just for use by the user to hook up arbitrary data with this
253 sv. This one is generally manipulated through sethdr and gethdr calls.
254 Smart references and transformations: slicing and dicing
256 Smart references and most other fundamental functions operating on
257 ndarrays are implemented via transformations (as mentioned above) which
258 are represented by the type "pdl_trans" in PDL.
259 A transformation links input and output ndarrays and contains all the
261 infrastructure that defines how:
262 • output ndarrays are obtained from input ndarrays;
264 • changes in smart-linked output ndarrays (e.g. the child of a sliced
266 parent ndarray) are flowed back to the input ndarray in
267 transformations where this is supported (the most often used
268 example being "slice" here);
269 • datatype and size of output ndarrays that need to be created are
271 obtained.
272 In general, executing a PDL function on a group of ndarrays results in
274 creation of a transformation of the requested type that links all input
275 and output arguments (at least those that are ndarrays). In PDL
276 functions that support data flow between input and output args (e.g.
277 "slice", "index") this transformation links parent (input) and child
278 (output) ndarrays permanently until either the link is explicitly
279 broken by user request ("sever" at the Perl level) or all parents and
280 children have been destroyed. In those cases the transformation is
281 lazy-evaluated, e.g. only executed when ndarray values are actually
282 accessed.
283 In non-flowing functions, for example addition ("+") and inner products
285 ("inner"), the transformation is installed just as in flowing functions
286 but then the transformation is immediately executed and destroyed
287 (breaking the link between input and output args) before the function
288 returns.
289 It should be noted that the close link between input and output args of
291 a flowing function (like slice) requires that ndarray objects that are
292 linked in such a way be kept alive beyond the point where they have
293 gone out of scope from the point of view of Perl:
294 $x = zeroes(20);
296 $y = $x->slice('2:4');
297 undef $x; # last reference to $x is now destroyed
298 Although $x should now be destroyed according to Perl's rules the
300 underlying "pdl" structure must actually only be freed when $y also
301 goes out of scope (since it still references internally some of $x's
302 data). This example demonstrates that such a dataflow paradigm between
303 PDL objects necessitates a special destruction algorithm that takes the
304 links between ndarrays into account and couples the lifespan of those
305 objects. The non-trivial algorithm is implemented in the function
306 "pdl_destroy" in pdlapi.c. In fact, most of the code in pdlapi.c is
307 concerned with making sure that ndarrays ("pdl *"s) are created,
308 updated and freed at the right times depending on interactions with
309 other ndarrays via PDL transformations (remember, "pdl_trans").
310 Accessing children and parents of an ndarray
312 When ndarrays are dynamically linked via transformations as suggested
313 above input and output ndarrays are referred to as parents and
314 children, respectively.
315 An example of processing the children of an ndarray is provided by the
317 method "badflag" in PDL::Bad (before 2.079, it only operated on the
318 children, though now it propagates to parents too).
319 Consider the following situation:
321 pdl> $x = rvals(7,7,{Centre=>[3,4]});
323 pdl> $y = $x->slice('2:4,3:5');
324 pdl> ? vars
325 PDL variables in package main::
326 Name Type Dimension Flow State Mem
328 ----------------------------------------------------------------
329 $x Double D [7,7] P 0.38Kb
330 $y Double D [3,3] -C 0.00Kb
331 Now, if I suddenly decide that $x should be flagged as possibly
333 containing bad values, using
334 pdl> $x->badflag(1)
336 then I want the state of $y - its child - to be changed as well (since
338 it will either share or inherit some of $x's data and so be also bad),
339 so that I get a 'B' in the State field:
340 pdl> ? vars
342 PDL variables in package main::
343 Name Type Dimension Flow State Mem
345 ----------------------------------------------------------------
346 $x Double D [7,7] PB 0.38Kb
347 $y Double D [3,3] -CB 0.00Kb
348 This bit of magic is performed by the "propagate_badflag" function,
350 which is in pdlapi.c. Given an ndarray ("pdl *it"), the routine loops
351 through each "pdl_trans" structure, where access to this structure is
352 provided by the "PDL_CHILDLOOP_THISCHILD" macro. The children of the
353 ndarray are stored in the "pdls" array, after the parents, hence the
354 loop from "i = ...nparents" to "i = ...npdls - 1". Once we have the
355 pointer to the child ndarray, we can do what we want to it; here we
356 change the value of the "state" variable, but the details are
357 unimportant). What is important is that we call "propagate_badflag" on
358 this ndarray, to ensure we loop through its children. This recursion
359 ensures we get to all the offspring of a particular ndarray.
360 Access to parents is similar, with the "for" loop replaced by:
362 for( i = 0;
364 i < trans->vtable->nparents;
365 i++ ) {
366 /* do stuff with parent #i: trans->pdls[i] */
367 }
368 What's in a transformation ("pdl_trans")
370 All transformations are implemented as structures
371 struct pdl_trans {
373 int magicno; /* to detect memory overwrites */
374 short flags; /* state of the trans */
375 pdl_transvtable *vtable; /* the all important vtable */
376 int __datatype; /* the type of the transformation */
377 void *params; /* Opaque pointer to "compiled representation" of transformation */
378 pdl *pdls[]; /* The pdls involved in the transformation */
379 };
380 The "params" member is an opaque pointer, typically to a C struct that
382 holds the "compiled representation" (generated by PDL::PP), and is the
383 way that information like "OtherPars" etc get communicated from
384 invoking code to the "redodims" function - effectively a closure, in
385 Perl/LISP terms. This is necessary because "redodims" is called by a
386 PDL-internal function, and therefore must have a fixed parameter list.
387 The transformation identifies all "pdl"s involved in the trans
389 pdl *pdls[];
391 This is a C99 "incomplete array type", and works because it is at the
393 end of the struct - PDL allocates the correct amount of memory based on
394 the "npdls" member of the "vtable". The trans records the state
395 short flags;
397 and the datatype
399 int __datatype;
401 of the trans (to which all ndarrays must be converted unless they are
403 explicitly typed, PDL functions created with PDL::PP make sure that
404 these conversions are done as necessary). Most important is the pointer
405 to the vtable (virtual table) that contains the actual functionality
406 pdl_transvtable *vtable;
408 The vtable structure in turn looks something like (slightly simplified
410 from pdl.h for clarity)
411 typedef struct pdl_transvtable {
413 int flags;
414 int nparents; /* number of parent pdls (input) */
415 int npdls; /* number of child pdls (output) */
416 char *per_pdl_flags; /* optimization flags */
417 pdl_error (*redodims)(pdl_trans *tr); /* figure out dims of children */
418 pdl_error (*readdata)(pdl_trans *tr); /* flow parents to children */
419 pdl_error (*writebackdata)(pdl_trans *tr); /* flow backwards */
420 pdl_error (*freetrans)(pdl_trans *tr, char);
421 int structsize;
422 char *name; /* the function's name */
423 } pdl_transvtable;
424 The transformation and vtable code is hardly ever written by hand but
426 rather generated by PDL::PP from concise descriptions.
427 Certain types of transformations can be optimized very efficiently
429 obviating the need for explicit "readdata" and "writebackdata" methods.
430 Those transformations are called pdl_vaffine. Most dimension
431 manipulating functions (e.g., "slice", "xchg") belong to this class.
432 The basic trick is that parent and child of such a transformation work
434 on the same (shared) block of data which they just choose to interpret
435 differently (by using different "dims", "dimincs" and "offs" on the
436 same data, compare the "pdl" structure above). Each operation on an
437 ndarray sharing data with another one in this way is therefore
438 automatically flowed from child to parent and back -- after all they
439 are reading and writing the same block of memory. This is currently not
440 Perl thread safe -- no big loss since the whole PDL core is not
441 reentrant.
442 Callback functions
444 redodims
445 Works out the dimensions of ndarrays that need to be created and is
447 called from within the API function that should be called to ensure
448 that the dimensions of an ndarray are accessible (pdlapi.c):
449 pdl_error pdl_make_physdims(pdl *it)
451 readdata and writebackdata
453 Responsible for the actual computations of the child data from the
455 parents or parent data from those of the children, respectively (the
456 dataflow aspect). "readdata" populates the children from the parents,
457 and "writebackdata" implements updating the parent(s) from the
458 child(ren) if dataflow is part of that transformation. The PDL core
459 makes sure that these are called as needed when ndarray data is
460 accessed (lazy-evaluation). The general API function to ensure that an
461 ndarray is up-to-date is
462 pdl_error pdl_make_physvaffine(pdl *it)
464 which should be called before accessing ndarray data from XS/C (see
466 Core.xs for some examples).
467 freetrans
469 Frees dynamically allocated memory associated with the trans as needed.
471 If "redodims" has previously been called, it will free any vaffine-
472 associated memory. If the "destroy" parameter is true, it will also
473 free any bespoke "params"-connected memory - this will not be the case
474 if called before doing another "redodims". Again, functions built with
475 PDL::PP make sure that freeing via these callbacks happens at the right
476 times.
477 Signatures: broadcasting over elementary operations
479 Most of that functionality of PDL broadcasting (automatic iteration of
480 elementary operations over multi-dim ndarrays) is implemented in the
481 file pdlbroadcast.c.
482 The PDL::PP generated functions (in particular the "readdata" and
484 "writebackdata" callbacks) use this infrastructure to make sure that
485 the fundamental operation implemented by the trans is performed in
486 agreement with PDL's broadcasting semantics.
487 Defining new PDL functions -- Glue code generation
489 Please, see PDL::PP and examples in the PDL distribution.
490 Implementation and syntax are currently far from perfect but it does a
491 good job!
492 The Core struct
494 As discussed in PDL::API, PDL uses a pointer to a structure to allow
495 PDL modules access to its core routines. The definition of this
496 structure (the "Core" struct) is in pdlcore.h (created by pdlcore.h in
497 Basic/Core) and looks something like
498 /* Structure to hold pointers core PDL routines so as to be used by
500 * many modules
501 */
502 struct Core {
503 I32 Version;
504 pdl* (*SvPDLV) ( SV* );
505 void (*SetSV_PDL) ( SV *sv, pdl *it );
506 pdl* (*pdlnew) ( );
507 pdl* (*tmp) ( );
508 pdl* (*create) (int type);
509 pdl_error (*destroy) (pdl *it);
510 ...
511 }
512 typedef struct Core Core;
513 The first field of the structure ("Version") is used to ensure
515 consistency between modules at run time; the following code is placed
516 in the BOOT section of the generated xs code:
517 if (PDL->Version != PDL_CORE_VERSION)
519 Perl_croak(aTHX_ "Foo needs to be recompiled against the newly installed PDL");
520 If you add a new field to the Core struct you should:
522 • discuss it on the pdl porters email list
524 (pdl-devel@lists.sourceforge.net) and use the techniques in
525 PDL::FAQ 4.11.
526 • increase by 1 the value of the "PDL_CORE_VERSION" C macro used to
528 populate the Version field, in pdlcore.h.
529 • add documentation (e.g. to PDL::API) if it's a "useful" function
531 for external module writers (as well as ensuring the code is as
532 well documented as the rest of PDL ;)
533
535 This description is far from perfect. If you need more details or
536 something is still unclear please ask on the pdl-devel mailing list
537 (pdl-devel@lists.sourceforge.net).
538
540 Copyright(C) 1997 Tuomas J. Lukka (lukka@fas.harvard.edu), 2000 Doug
541 Burke (djburke@cpan.org), 2002 Christian Soeller & Doug Burke, 2013
542 Chris Marshall.
543perl v5.38.0 2023-07-21 INTERNALS(1)