|
PDL::Internals - description of some aspects of the current internals |
pdl_trans)
PDL::Internals - description of some aspects of the current internals
This document explains various aspects of the current implementation of PDL. If you just want to use PDL for something, you definitely do not need to read this. Even if you want to interface your C routines to PDL or create new PDL::PP functions, you do not need to read this man page (though it may be informative). This document is primarily intended for people interested in debugging or changing the internals of PDL. To read this, a good understanding of the C language and programming and data structures in general is required, as well as some Perl understanding. If you read through this document and understand all of it and are able to point what any part of this document refers to in the PDL core sources and additionally struggle to understand PDL::PP, you will be awarded the title ``PDL Guru'' (of course, the current version of this document is so incomplete that this is next to impossible from just these notes).
Warning: If it seems that this document has gotten out of date, please inform the PDL porters email list (pdl-porters@jach.hawaii.edu) This may well happen.
The pdl data object is generally an opaque scalar reference into a
pdl structure in memory. Alternatively, it may be a hash reference with
the PDL field containing the scalar reference (this makes overloading
piddles easy, see PDL::Objects). You can easily find out
at the Perl level which type of piddle you are dealing with. The example
code below demonstrates how to do it:
# check if this a piddle
die "not a piddle" unless UNIVERSAL::isa($pdl, 'PDL');
# is it a scalar ref or a hash ref?
if (UNIVERSAL::isa($pdl, "HASH")) {
die "not a valid PDL" unless exists $pdl->{PDL} &&
UNIVERSAL::isa($pdl->{PDL},'PDL');
print "This is a hash reference,",
" the PDL field contains the scalar ref\n";
} else {
print "This is a scalar ref that points to address $$pdl in memory\n";
}
The scalar reference points to the numeric address of a C structure of
type pdl which is defined in pdl.h. The mapping between the
object at the Perl level and the C structure containing the actual
data and structural that makes up a piddle is done by the PDL typemap.
The functions used in the PDL typemap are defined pretty much at the top
of the file pdlcore.h. So what does the structure look like:
struct pdl {
unsigned long magicno; /* Always stores PDL_MAGICNO as a sanity check */
/* This is first so most pointer accesses to wrong type are caught */
int state; /* What's in this pdl */
pdl_trans *trans; /* Opaque pointer to internals of transformation from
parent */
pdl_vaffine *vafftrans;
void* sv; /* (optional) pointer back to original sv.
ALWAYS check for non-null before use.
We cannot inc refcnt on this one or we'd
never get destroyed */
void *datasv; /* Pointer to SV containing data. Refcnt inced */
void *data; /* Null: no data alloced for this one */
int nvals; /* How many values allocated */
int datatype;
PDL_Long *dims; /* Array of data dimensions */
PDL_Long *dimincs; /* Array of data default increments */
short ndims; /* Number of data dimensions */
unsigned char *threadids; /* Starting index of the thread index set n */
unsigned char nthreadids;
pdl *progenitor; /* I'm in a mutated family. make_physical_now must
copy me to the new generation. */
pdl *future_me; /* I'm the "then" pdl and this is my "now" (or more modern
version, anyway */
pdl_children children;
short living_for; /* perl side not referenced; delete me when */
PDL_Long def_dims[PDL_NDIMS]; /* Preallocated space for efficiency */
PDL_Long def_dimincs[PDL_NDIMS]; /* Preallocated space for efficiency */
unsigned char def_threadids[PDL_NTHREADIDS];
struct pdl_magic *magic;
void *hdrsv; /* "header", settable from outside */
};
This is quite a structure for just storing some data in - what is going on?
void *datasv;
which is really a pointer to a Perl SV structure (SV *). The SV is
expected to be representing a string, in which the data of the piddle
is stored in a tightly packed form. This pointer counts as a reference
to the SV so the reference count has been incremented when the SV *
was placed here (this reference count business has to do with Perl's
garbage collection mechanism -- don't worry if this doesn't mean much
to you). This pointer is allowed to have the value NULL which
means that there is no actual Perl SV for this data - for instance, the data
might be allocated by a mmap operation. Note the use of an SV*
was purely for convenience, it allows easy transformation of
packed data from files into piddles. Other implementations are not
excluded.
The actual pointer to data is stored in the member
void *data;
which contains a pointer to a memory area with space for
int nvals;
data items of the data type of this piddle.
The data type of the data is stored in the variable
int datatype;
the values for this member are given in the enum pdl_datatypes (see
pdl.h). Currently we have byte, short, unsigned short, long, float and
double types, see also the PDL::Types manpage.
int ndims;
which shows how many entries there are in the arrays
PDL_Long *dims;
PDL_Long *dimincs;
These arrays are intimately related: dims gives the sizes of the dimensions
and dimincs is always calculated by the code
int inc = 1;
for(i=0; i<it->ndims; i++) {
it->dimincs[i] = inc; inc *= it->dims[i];
}
in the routine pdl_resize_defaultincs in pdlapi.c.
What this means is that the dimincs can be used to calculate the offset
by code like
int offs = 0;
for(i=0; i<it->ndims; i++) {
offs += it->dimincs[i] * index[i];
}
but this is not always the right thing to do, at least without checking for certain things first.
PDL_Long def_dims[PDL_NDIMS];
PDL_Long def_dimincs[PDL_NDIMS];
The dims and dimincs may be set to point to the beginning of these
arrays if ndims is smaller than or equal to the compile-time constant
PDL_NDIMS. This is important to note when freeing a piddle struct.
The same applies for the threadids:
unsigned char def_threadids[PDL_NTHREADIDS];
struct pdl_magic *magic;
is nonzero, the PDL has some magic attached to it. The implementation of magic can be gleaned from the file pdlmagic.c in the distribution.
int state;
The possible flags and their meanings are given in pdl.h.
These are mainly used to implement the lazy evaluation mechanism
and keep track of piddles in these operations.
$b = $a->slice("2:5");
$b .= 1;
will alter $a. So $b and $a know that they are connected
via a slice-transformation. This information is stored in the members
pdl_trans *trans;
pdl_vaffine *vafftrans;
Both $a (the parent) and $b (the child) store this information
about the transformation in appropriate slots of the pdl structure.
pdl_trans and pdl_vaffine are structures that we will look at in
more detail below.
void* sv;
in order to be able to return a reference to the user when he wants to inspect the transformation structure on the Perl side.
Also, we store an opaque
void *hdrsv;
which is just for use by the user to hook up arbitrary data with this sv. This one is generally manipulated through sethdr and gethdr calls.
=back
Smart references and most other fundamental functions
operating on piddles are implemented via transformations
(Aas mentioned above) which are represented by the type pdl_trans in PDL.
A transformation links input and output piddles and contains all the infrastructure that defines how
slice here).
In general, executing a PDL function on a group of piddles
results in creation of a transformation of the requested
type that links all input and output arguments (at least
those that are piddles). In PDL functions that support
data flow between input and output args (e.g. slice,
index) this transformation links parent (input) and
child (output) piddles permanently until either the link is
explicitly broken by user request (sever at the perl level)
or all parents and childen have been destroyed. In those
cases the transformation is lazy-evaluated, e.g. only executed
when piddle values are actually accessed.
In non-flowing functions, for example addition (+) and inner
products (inner), the transformation is installed just as
in flowing functions but then the transformation is immediately
executed and destroyed (breaking the link between input and output args)
before the function returns.
It should be noted that the close link between input and output args of a flowing function (like slice) requires that piddle objects that are linked in such a way be kept alive beyond the point where they have gone out of scope from the point of view of perl:
$a = zeroes(20);
$b = $a->slice('2:4');
undef $a; # last reference to $a is now destroyed
Although $a should now be destroyed according to perl's rules
the underlying pdl structure must actually only be freed when $b
also goes out of scope (since it still references
internally some of $a's data). This example demonstrates that such
a dataflow paradigm between PDL objects necessitates a special
destruction algorithm that takes the links between piddles
into account and couples the lifespan of those objects. The
non-trivial algorithm is implemented in the function
pdl_destroy in pdlapi.c. In fact, most of the code
in pdlapi.c and pdlfamily.c is concerned with
making sure that piddles (pdl *s) are created, updated
and freed at the right times depending on interactions
with other piddles via PDL transformations (remember, pdl_trans).
When piddles are dynamically linked via transformations as suggested above input and output piddles are referred to as parents and children, respectively.
An example of processing the children of a piddle is provided
by the baddata method of PDL::Bad (only available if you
have comiled PDL with the WITH_BADVAL option set to 1,
but still useful as an example!).
Consider the following situation:
perldl> $a = rvals(7,7,Centre=>[3,4]);
perldl> $b = $a->slice('2:4,3:5');
perldl> ? vars
PDL variables in package main::
Name Type Dimension Flow State Mem ---------------------------------------------------------------- $a Double D [7,7] P 0.38Kb $b Double D [3,3] VC 0.00Kb
Now, if I suddenly decide that $a should be flagged as possibly
containing bad values, using
perldl> $a->baddata(1)
then I want the state of $b - it's child - to be changed as
well (since it will either share or inherit some of $a's data and
so be also bad), so that I get a 'B' in the State field:
perldl> ? vars PDL variables in package main::
Name Type Dimension Flow State Mem ---------------------------------------------------------------- $a Double D [7,7] PB 0.38Kb $b Double D [3,3] VCB 0.00Kb
This bit of magic is performed by the propogate_badflag function,
which is listed below:
/* newval = 1 means set flag, 0 means clear it */ /* thanks to Christian Soeller for this */
void propogate_badflag( pdl *it, int newval ) {
PDL_DECL_CHILDLOOP(it)
PDL_START_CHILDLOOP(it)
{
pdl_trans *trans = PDL_CHILDLOOP_THISCHILD(it);
int i;
for( i = trans->vtable->nparents;
i < trans->vtable->npdls;
i++ ) {
pdl *child = trans->pdls[i];
if ( newval ) child->state |= PDL_BADVAL;
else child->state &= ~PDL_BADVAL;
/* make sure we propogate to grandchildren, etc */
propogate_badflag( child, newval );
} /* for: i */
}
PDL_END_CHILDLOOP(it)
} /* propogate_badflag */
Given a piddle (pdl *it), the routine loops through each
pdl_trans structure, where access to this structure is provided by the
PDL_CHILDLOOP_THISCHILD macro.
The children of the piddle are stored in the pdls array, after the
parents, hence the loop from i = ...nparents to
i = ...nparents - 1.
Once we have the pointer to the child piddle, we can do what we want to
it; here we change the value of the state variable, but the details
are unimportant).
What is important is that we call propogate_badflag on this
piddle, to ensure we loop through its children. This recursion
ensures we get to all the offspring of a particular piddle.
Access to parents is similar, with the for loop replaced by:
for( i = 0;
i < trans->vtable->nparents;
i++ ) {
/* do stuff with parent #i: trans->pdls[i] */
}
pdl_trans)All transformations are implemented as structures
struct XXX_trans {
int magicno; /* to detect memory overwrites */
short flags; /* state of the trans */
pdl_transvtable *vtable; /* the all important vtable */
void (*freeproc)(struct pdl_trans *); /* Call to free this trans
(in case we had to malloc some stuff dor this trans) */
pdl *pdls[NP]; /* The pdls involved in the transformation */
int __datatype; /* the type of the transformation */
/* in general more members
/* depending on the actual transformation (slice, add, etc)
*/
};
The transformation identifies all pdls involved in the trans
pdl *pdls[NP];
with NP depending on the number of piddle args of the particular
trans. It records a state
short flags;
and the datatype
int __datatype;
of the trans (to which all piddles must be converted unless they are explicitly typed, PDL functions created with PDL::PP make sure that these conversions are done as necessary). Most important is the pointer to the vtable (virtual table) that contains the actual functionality
pdl_transvtable *vtable;
The vtable structure in turn looks something like (slightly simplified from pdl.h for clarity)
typedef struct pdl_transvtable {
pdl_transtype transtype;
int flags;
int nparents; /* number of parent pdls (input) */
int npdls; /* number of child pdls (output) */
char *per_pdl_flags; /* optimization flags */
void (*redodims)(pdl_trans *tr); /* figure out dims of children */
void (*readdata)(pdl_trans *tr); /* flow parents to children */
void (*writebackdata)(pdl_trans *tr); /* flow backwards */
void (*freetrans)(pdl_trans *tr); /* Free both the contents and it of
the trans member */
pdl_trans *(*copy)(pdl_trans *tr); /* Full copy */
int structsize;
char *name; /* For debuggers, mostly */
} pdl_transvtable;
We focus on the callback functions:
void (*redodims)(pdl_trans *tr);
redodims will work out the dimensions of piddles that need
to be created and is called from within the API function that
should be called to ensure that the dimensions of a piddle are
accessible (pdlapi.c):
void pdl_make_physdims(pdl *it)
readdata and writebackdata are responsible for the actual
computations of the child data from the parents or parent data
from those of the children, respectively (the dataflow aspect).
The PDL core makes sure that these are called as needed when
piddle data is accessed (lazy-evaluation). The general API
function to ensure that a piddle is up-to-date is
void pdl_make_physvaffine(pdl *it)
which should be called before accessing piddle data from XS/C (see Core.xs for some examples).
freetrans frees dynamically allocated memory associated
with the trans as needed and copy can copy the transformation.
Again, functions built with PDL::PP make sure that copying
and freeing via these callbacks happens at the right times. (If they
fail to do that we have got a memory leak -- this has happened in
the past ;).
The transformation and vtable code is hardly ever written by hand but rather generated by PDL::PP from concise descriptions.
Certain types of transformations can be optimized very
efficiently obviating the need for explicit readdata
and writebackdata methods. Those transformations are
called pdl_vaffine. Most dimension manipulating
functions (e.g., slice, xchg) belong to this class.
The basic trick is that parent and child of such a transformation work
on the same (shared) block of data which they just choose
to interpret differently (by dusing different dims, dimincs and
offs on the same data, compare the pdl structure above).
Each operation on a piddle sharing
data with another one in this way is therefore automatically flown
from child to parent and back -- after all they are reading and writing
the same block of memory. This is currently not perl thread safe --
no big loss since the whole PDL core is not reentrant
(perl threading != PDL threading!).
Most of that functionality of PDL threading (automatic iteration of elemntary operations over multidim piddles) is implemented in the file pdlthread.c.
The PDL::PP generated functions (in particular the
readdata and writebackdata callbacks) use this infrastructure to
make sure that the fundamental operation implemented by the
trans is performed in agreement with PDL's threading semantics.
Please, see the PDL::PP manpage and examples in the PDL distribution. Implementation and syntax are currently far from perfect but it does a good job!
As discussed in PDL::API, PDL uses a pointer to a structure
to allow PDL modules access to its core routines. The definition of this
structure (the Core struct) is in pdlcore.h (created by
pdlcore.h.PL in Basic/Core) and looks something like
/* Structure to hold pointers core PDL routines so as to be used by
* many modules
*/
struct Core {
I32 Version;
pdl* (*SvPDLV) ( SV* );
void (*SetSV_PDL) ( SV *sv, pdl *it );
#if defined(PDL_clean_namespace) || defined(PDL_OLD_API)
pdl* (*new) ( ); /* make it work with gimp-perl */
#else
pdl* (*pdlnew) ( ); /* renamed because of C++ clash */
#endif
pdl* (*tmp) ( );
pdl* (*create) (int type);
void (*destroy) (pdl *it);
...
}
typedef struct Core Core;
The first field of the structure (Version) is used to ensure
consistency between modules at run time; the following code
is placed in the BOOT section of the generated xs code:
if (PDL->Version != PDL_CORE_VERSION) Perl_croak(aTHX_ "Foo needs to be recompiled against the newly installed PDL");
If you add a new field to the Core struct you should:
$pdl_core_version variable in
pdlcore.h.PL. This sets the value of the
PDL_CORE_VERSION C macro used to populate the Version field
This description is far from perfect. If you need more details or something is still unclear please ask on the pdl-porters mailing list (pdl-porters@jach.hawaii.edu)
Copyright(C) 1997 Tuomas J. Lukka (lukka@fas.harvard.edu),
2000 Doug Burke (djburke@cpan.org), 2002 Christian Soeller & Doug Burke.
Redistribution in the same form is allowed but reprinting requires a permission from the author.
|
PDL::Internals - description of some aspects of the current internals |