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