Balisage Paper: Platform Independence 2010 - Helping Documents Fly Well in Emerging Architectures

Introduction

Ever faster sequential computations in single ever-larger memory spaces has been "just how it is" in mainstream computing for about a generation - long enough for design considerations that are actually dependent on this environment to become invisible, unthought assumptions. After many years on the sidelines, parallel architectures are becoming mainstream, with more parallelism now the obvious way to gain more performance. Memory performance has been growing more slowly, so feeding data to and from all these parallel cycles is also a major challenge, with platform architecture solutions generally focussing on efficient ways to move data through deep hierarchies spanning the range from distant network resources to on-chip caches. Large and distributed data in particular needs to move efficiently through many layers of memory hierarchy, with each layer behaving as a cache with respect to the previous layer, that is, being significantly smaller and faster, and with a different block or page size.

What does this have to do with XML? Surely all this is under the hood or behind the scenes, something for compiler designers, software architects and other non-content people to worry about? After all, a platform is a just a platform, and XML and many XML tools are platform-independent.

To an extent this is true. Compiler designers, software architects and especially database vendors are busy worrying right now, and much thought from the Balisage community and others will also undoubtedly go into making basic XML tools work well on the new platforms. However, notwithstanding these efforts, data designed with due attention to the fundamental characteristics of emerging platform architectures are likely to fare better, especially in speed of processing, than data designed for the "old world".

Against this background, the premise underlying this paper is that since parallel processing and managing data flows within memory hierarchies are increasingly prominent in mainstream platform architecture, any large data structure, or collection of data that is usually processed together, now needs to be more or less parallel-friendly, cache-oblivious, and distribution-tolerant, to be really platform-independent - and this includes XML instances. This paper is about the attention we need to pay now as designers of XML content to the structural design patterns that will promote or prevent our data structures being the ones that happen to start running unexpectedly slowly next year or the year after.

What are these emerging architectures?

This section provides a concise account of emerging processor architectures and the state of the art in data access. Implications for platform-independent XML content design are discussed in the following section.

Platform Independence 2010++?

So what is it to be platform independent in 2010 and beyond? What do we need to be independent of, specifically? In simple terms, the key platform features are:

Any one platform can be assumed to have clever low-level software that is designed to hide its complexity and weirdness, so that everything still works correctly. Preserving correct processing is a high priority in designing new processor architectures with forward compatibility from older ones - however it turns out that data designed for the "old world" , although not broken, can be unexpectedly slow in emerging architectures. This can also lead indirectly to faults, for example when timing assumptions are broken.

The main evidence I have for this is anecdotal - side-remarks in talks and water-cooler chat with infrastructure-specialist colleagues who are managing a range of data-intensive applications in a growing data centre. Suffice it to say that there are people who earn a living advising how to get this right, and that my colleagues tell me that more than one well-established product has needed updates to resolve performance problems in a more distributed, parallel environment.

Abstracting away from platform features into data processing, the key features are as follows.

The balance of emphasis between these features varies across the different architectures involved, for example scheduling dependencies and data exchange (rather than just data partitioning) become more prominent the more communication is needed between pieces of computation. Data exchange operates at different scales such as a multicore chip passing data between independently processing cores that have separate caches, and a multi-processor architecture passing data between processors (such as the common example of a desktop computer with a separate graphics processor).

A fundamental research result regarding data exchange is that, in the general case where the structures at each end are different, and a computation is needed to map data from one to the other, the computational complexity of a data exchange is exponentially related to the complexity of the data schemas at each end. The complexity of a data schema is a combination of complexity measures on the actual data structure and how it is described (Kolaitis et al 06).

This result is no great surprise, since data exchange feels like a hard problem in practice. However, when data exchange becomes a larger proportionate part of general computation, its exponential general complexity properties suggest that there are significant benefits to be gained from keeping data structures and the ways they are described as simple as possible.

Partitioning data and computation is a more familiar problem, though one effect of a generation of ever-more-capable sequential processing environments with ever-larger memory spaces has been a tendency to regard such concerns as rather old-fashioned. High performance computing for scientific data analysis has kept this area of work alive, especially in relation to arrays of data and matrix computations (for example Lee & Zedem 2002) and automatic data partitioning on this kind of data in XML has also been investigated (Head et al 09).

Design Principles for Platform-Independence

This section suggests a few rules of thumb that are likely to make larger documents, and smaller documents (such as messages) that turn up in large numbers, more truly platform independent over these changes in processing architecture. Some of the rules come naturally when writing or designing documents by hand, but are pretty easy to break or ignore when marked-up data is generated by a program. Others may look like obvious bad practice from the point of view of writing and maintaining documents by hand, but look more like candidates for sensible design trade-offs when marked-up data is being generated by a program. (Note that "generated by a program" includes using one of the many authoring tools that provide an illusion of manual editing. If you are not seeing all the grim details of the pointy brackets as you type, then your data is being generated by a program.)

Note that it is specifically NOT assumed here that the current usual-suspect XML processing tools will be used to process or pre-process the document instances concerned. These tools may or may not be able to overcome fundamental problems in data characterstics " under the hood ", even if rewritten, and new tools will come. The only assumptions made below are the structural properties of XML instances.

Examples

The performance penalties discussed above would be expected to be felt mainly at large scale, that is, on large documents or high volume processing of smaller documents. However, the structural patterns in the rules of thumb can be illustrated using small examples, and that is the purpose of this section.

Action at a distance, "shopping local", and replication

These patterns are illustrated in this section using two contrasting examples. Each example is based on the structural characteristics of a (different) real data format designed for exchanging information extracted from patient records.

The first example has instances divided into in two main parts. First, a list of entities (people, roles and locations), and second, a list of recorded events involving these entitites. Entities are included in events by reference to a unique identifier for each entity.

As the number of events grows, then because a patient will tend to interact with the same people and be treated in the same places, the proportion of entities compared to events will decrease.

There are two motivating ideas underlying these design features. One is to minimize repetition of data, and the other is to facilitate data transfer between instances of software applications having similar (relational) database structures that are closely aligned with the structure of the data. These aims lead to a structure that explicitly avoids replication and has a strong tendency not to "shop local". In addition, the references to identifiers are well hidden in the data from the point of view of XML parsing, and the majority of references are between two subtrees that diverge near the root of the document (" action at a distance").

Figure 1: Example 1

<?xml version="1.0" encoding="UTF-8"?>
<record>
    <entities>
        <person>
            <id>FF138AF1-F3BC-4BF7-B45C-427E012BA3F4</id>
            <dateOfBirth>1987-11-20</dateOfBirth>
            <name>...</name>
            <address>...</address>
        </person>
        <person>
            <id>BBBBE23A-A9D1-A411-F824-9F7A00A33757</id>
            <dateOfBirth>1987-11-20</dateOfBirth>
            <name>...</name>
            <address>...</address>
        </person>
        <location>
            <id>4B98A89C-41AD-4425-B6CF-17DE8C779FC7</id>
            <name>...</name>
            <address>...</address>
        </location>
        <role>
            <id>8533C566-74FB-4176-8EFE-13E3FCE5B3A6</id>
            <name>General Practitioner</name>
            <moreAboutRole>...</moreAboutRole>
        </role>
        <practitioner>
            <id>3CBA0926-1E25-4B0E-AAFC-F9CF02F8596B</id>
            <person>BBBBE23A-A9D1-A411-F824-9F7A00A33757</person>
            <role>8533C566-74FB-4176-8EFE-13E3FCE5B3A6</role>
        </practitioner>
        <patient>
            <id>A17B8BFA-3A2B-4796-87ED-F9A4D7375C3D</id>
            <pasNumber>39752746</pasNumber>
            <patientPerson>FF138AF1-F3BC-4BF7-B45C-427E012BA3F4</patientPerson>
        </patient>
    </entities>
    <events>
        <encounter>
            <id>97E037BE-4CBE-46BA-98F8-3BA6B4DA3D1C</id>
            <date>2010-04-01</date>
            <patient>A17B8BFA-3A2B-4796-87ED-F9A4D7375C3D</patient>
            <practitioner>3CBA0926-1E25-4B0E-AAFC-F9CF02F8596B</practitioner>
            <location>4B98A89C-41AD-4425-B6CF-17DE8C779FC7</location>
        </encounter>
    </events>
    </record>

In the second example, data about the people and places involved in a care event are given directly in each event subtree of the record extract. This data format was designed to convey information from a number of different software applications into a common store, from which it is then retrieved on a per-event basis. An explicit design criterion was to make no assumptions about the internal structure of the data store, and in the real situation this is based on, there are several such stores with different internal database structures.

This example also illustrates the role of replicating subtrees of data. A location address may appear many times, however the benefits of replication were judged to outweigh the costs, and the sending system is unlikely to make errors putting the same data into a number of events in a transferred record.

Figure 2: Example 2

<?xml version="1.0" encoding="UTF-8"?>
<Record>
<Event>
    <EffectiveTime>2008-04-23T15:10:00.0Z</EffectiveTime>
    <EventType>
        <IdValue>[Identifier for this event type]</IdValue>
    </EventType>
    <PatientDetails>
        <NHSnumber>
            <IdValue>1234567890</IdValue>
        </NHSnumber>
        <Name>...</Name>
        <Address>...</Address>
    </PatientDetails>
    <ResponsiblePerson>
        <StructuredName>
            <Title>Dr</Title>
            <GivenName>Local</GivenName>
            <FamilyName>Doctor</FamilyName>
        </StructuredName>
    </ResponsiblePerson>
    <Role>
        <IdValue>[role of responsible person]</IdValue>
    </Role>
    <Location>
        <StructuredAddress>
            <PropertyNumber>65</PropertyNumber>
            <AddressLine>Festaville Way</AddressLine>
            <AddressLine>Limnoleon</AddressLine>
            <AddressLine>Cranmore Regis</AddressLine>
        </StructuredAddress>
        <PostCode>LL99 3BB</PostCode>
    </Location>
    <LocationType>
        <IdValue>[Identifier for location type]</IdValue>
    </LocationType>
</Event>
</Record>
                

Variation in content between apparently similar things

The next example illustrates in principle how parallel processing of instances of the same element is slowed down by optionality in the data, in a processor that runs the same instruction stream in parallel on many data instances (SIMD). Each picture in the series shows the effect of progressively more variation between instances. Coloured cells indicate steps where no progress is made in processing that element.

The first picture below shows element instances with no variation at all, and there is no loss of performance. In the next, some items are optional. Any instance that lacks an optional item will be waiting while the other instances use that part of the instruction stream. The next one after shows what happens when a content model has a choice of sequences of elements. Finally, the fourth picture shows the result of having many possible options (for example, a rich XML vocabulary) with only a few used in any one data instance.

Figure 3: No optionality

Figure 4: Sparse optionality

Figure 5: Alternative substructures

Figure 6: Selective use of a large vocabulary

A simple count provides a rough indication of the magnitude of the effect. Taking the content of the example element only, in the first case, all steps are active. In the second, there are 5 idle steps out of 40, giving a crude efficiency measure of 87.5%. In the third case, 24 steps out of 40 are idle, i.e. 45% are active. In the final case, the majority of the steps relate to options not represented in the data, and only 4 steps out of 40 are active, i.e. 10%.

It must be emphasized that this is only a rough indication in principle; real effects will depend on a combination of data structures, application-level algorithms, programming language implementations, and operating system and processor strategies. However, even this crude analysis indicates the potential value of, for example, reconfiguring messages that have repetitive internal structure to use different element names in preference to naming elements by role and varying their internal structure, in order to provide easy opportunities for efficient data-parallel processing.

Conclusion

Only experience will show conclusively what effect emerging architectures may have on processing XML and other markup language instances. It just might turn out that the under-the-hood gnomes in the new architectures are so clever that most document and data designers can safely ignore these issues. However, the factors discussed above suggest that developers and owners of XML vocabularies, document types and data architectures should give some thought to the effect of emerging architectures on the realities of platform-independence.

This paper has focussed strongly on XML instances, independent from schemas, data models and processing models. Thorough consideration of these from the perspective of platform independence on emerging archtitectures may well either show some of the concerns in the paper to be groundless, or (more likely) yield more refined guidance on design principles. In particular, it is worth noting that the functional style of XSLT, and the explicitly context-limited formal semantics of XQuery, are both favourable characteristics (XPath/XQuery formal semantics, XPath/XQuery data model, XSLT 2.0) .

Another possible area of further work would be to analyse data exchange complexity specifically for XML to XML data exchanges. Theoretical work on data exchange complexity mostly uses relational database schemas as a reference model of data structure, and the work on XML-to-XML data exchange that came to light in researching this paper (though well short of a thorough literature review on the topic) indicated a tendency to work from oversimplified models of XML without apparent knowledge of foundational XML-related work such as the XPath/XQuery data model and formal semantics.