1INTERNALS(1) User Contributed Perl Documentation INTERNALS(1)
2
3
4
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
33 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
37 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
45 # 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
57 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
64 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
69 pdl_trans *trans_parent; /* Opaque pointer to internals of transformation from
70 parent */
71
72 pdl_vaffine *vafftrans;
73
74 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
79 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
87 unsigned char *broadcastids; /* Starting index of the broadcast index set n */
88 unsigned char nbroadcastids;
89
90 pdl_trans_children trans_children;
91
92 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
96 struct pdl_magic *magic;
97
98 void *hdrsv; /* "header", settable from outside */
99 };
100
101 This is quite a structure for just storing some data in - what is going
102 on?
103
104 Data storage
105
106 We are going to start with some of the simpler members: first of all,
107 there is the member
108
109 void *datasv;
110
111 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
123 The actual pointer to data is stored in the member
124
125 void *data;
126
127 which contains a pointer to a memory area with space for
128
129 PDL_Indx nvals;
130
131 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
134 The data type of the data is stored in the variable
135
136 int datatype;
137
138 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
143 Dimensions
144
145 The number of dimensions in the ndarray is given by the member
146
147 int ndims;
148
149 which shows how many entries there are in the arrays
150
151 PDL_Indx *dims;
152 PDL_Indx *dimincs;
153
154 These arrays are intimately related: "dims" gives the sizes of the
155 dimensions and "dimincs" is always calculated by the code
156
157 PDL_Indx inc = 1;
158 for(i=0; i<it->ndims; i++) {
159 it->dimincs[i] = inc; inc *= it->dims[i];
160 }
161
162 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
165 PDL_Indx offs = 0;
166 for(i=0; i<it->ndims; i++) {
167 offs += it->dimincs[i] * index[i];
168 }
169
170 but this is not always the right thing to do, at least without checking
171 for certain things first.
172
173 Default storage
174
175 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
179 PDL_Indx def_dims[PDL_NDIMS];
180 PDL_Indx def_dimincs[PDL_NDIMS];
181
182 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
187 unsigned char def_broadcastids[PDL_NBROADCASTIDS];
188
189 Magic
190
191 It is possible to attach magic to ndarrays, much like Perl's own magic
192 mechanism. If the member pointer
193
194 struct pdl_magic *magic;
195
196 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
199 State
200
201 One of the first members of the structure is
202
203 int state;
204
205 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
209 Transformations and virtual affine transformations
210
211 As you should already know, ndarrays often carry information about
212 where they come from. For example, the code
213
214 $y = $x->slice("2:5");
215 $y .= 1;
216
217 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
220 pdl_trans *trans_parent;
221 pdl_vaffine *vafftrans;
222
223 Both $x (the parent) and $y (the child) store this information about
224 the transformation in appropriate slots of the "pdl" structure.
225
226 "pdl_trans" and "pdl_vaffine" are structures that we will look at in
227 more detail below.
228
229 The Perl SVs
230
231 When ndarrays are referred to through Perl SVs, we store an additional
232 reference to it in the member
233
234 void* sv;
235
236 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
239 Also, we store an opaque
240
241 void *hdrsv;
242
243 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
246 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
251 A transformation links input and output ndarrays and contains all the
252 infrastructure that defines how:
253
254 • output ndarrays are obtained from input ndarrays;
255
256 • 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
261 • datatype and size of output ndarrays that need to be created are
262 obtained.
263
264 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
275 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
281 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
286 $x = zeroes(20);
287 $y = $x->slice('2:4');
288 undef $x; # last reference to $x is now destroyed
289
290 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
302 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
307 An example of processing the children of an ndarray is provided by the
308 method "badflag" in PDL::Bad.
309
310 Consider the following situation:
311
312 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
317 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
322 Now, if I suddenly decide that $x should be flagged as possibly
323 containing bad values, using
324
325 pdl> $x->badflag(1)
326
327 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
331 pdl> ? vars
332 PDL variables in package main::
333
334 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
339 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
351 Access to parents is similar, with the "for" loop replaced by:
352
353 for( i = 0;
354 i < trans->vtable->nparents;
355 i++ ) {
356 /* do stuff with parent #i: trans->pdls[i] */
357 }
358
359 What's in a transformation ("pdl_trans")
360 All transformations are implemented as structures
361
362 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
371 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
378 The transformation identifies all "pdl"s involved in the trans
379
380 pdl *pdls[];
381
382 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
386 short flags;
387
388 and the datatype
389
390 int __datatype;
391
392 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
397 pdl_transvtable *vtable;
398
399 The vtable structure in turn looks something like (slightly simplified
400 from pdl.h for clarity)
401
402 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
415 The transformation and vtable code is hardly ever written by hand but
416 rather generated by PDL::PP from concise descriptions.
417
418 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
423 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
433 Callback functions
434 redodims
435
436 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
440 pdl_error pdl_make_physdims(pdl *it)
441
442 readdata and writebackdata
443
444 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
453 pdl_error pdl_make_physvaffine(pdl *it)
454
455 which should be called before accessing ndarray data from XS/C (see
456 Core.xs for some examples).
457
458 freetrans
459
460 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
468 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
473 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
478 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
483 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
489 /* 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
504 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
508 if (PDL->Version != PDL_CORE_VERSION)
509 Perl_croak(aTHX_ "Foo needs to be recompiled against the newly installed PDL");
510
511 If you add a new field to the Core struct you should:
512
513 • 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
517 • increase by 1 the value of the "PDL_CORE_VERSION" C macro used to
518 populate the Version field, in pdlcore.h.
519
520 • 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.
533
534
535
536perl v5.34.0 2022-02-28 INTERNALS(1)