From Offsets to Pointers
Current Status
Hail-lang values are represented in memory with a custom format, commonly referred to as the Region Value representation. For more details on that representation see the classes in is.hail.annotations, in particular, take a look at RegionValueBuilder.
Recall that arrays inside other data structures are represented as offsets that point to memory holding the length and the missing bits.
There is no way to refer to memory in a different region.
The Problem
In the current state, there is no easy way to execute a hail-lang expression that accesses data stored in two regions. For example, a hail-lang expression that reads data from the globals and reads data from the row or entry fields.
The current solution is to copy all necessary data into one region and execute the hail-lang expression with the single region.
Possible Solutions
To avoid all copies we must design a way to point to data in different regions.
- Use a few bits of the offset to mark the source region. De-referencing memory now requires a mask to the region identifier, a lookup of said identifier, and a second mask to get an offset in that region.
- Use actual memory addresses instead of offsets. De-referencing memory is a single machine operation. This requires that we use the
Longpointer methods insun.misc.Unsaferather than theObjectpointer +Longoffsets methods.
Both of the proposed solutions require that the referencee-region is longer lived than the referencer-region. If not, you have pointers to garbage / non-existing memory.
Both of the proposed solutions present de-serialization challenges. Hail currently doesn’t permit users to generate cyclic data, so we, at least, need not concern ourselves with that (for now). Some relevant work in the super-fast de-serialization is Frank McSherry’s Abomonation. Abomonation serializes by literally copying the bits of the data. In the case of Rust’s Vec<T> (which is essentially std::vector<T>), it’s a bit unclear, but I think he writes the length as 4 bytes followed by the data, in-line.
The simplest, correct thing for us to do is to simply chase pointers recursively writing the contents out in-line. For example,
{ a: int32
, b: array<int32>
, c: int32
}
is written as:
- first four bytes encode
a - next four bytes encode the length of
b - the contents of
bwritten in-line, all said: 4 * the length ofbbytes - final four bytes encode
c
Region.copyFrom is safe when copying from a longer lived buffer to a shorter lived buffer. It is only safe when copying from a shorter lived buffer to a longer lived buffer if the pointers point to data with lifetime equal to or longer than the target buffer. In general, we should avoid Region.copyFrom from a shorter-lived buffer to a longer-lived buffer. The same advice transitively applies to RegionValueBuilder.addRegionValue. copyFrom does not seem to be used elsewhere, which eases the necessary work.
Proposed Solution
I (in consultation with @cseed) propose we use actual memory addresses.
Aside: Eliminating RegionValue and Inverting the Flow of Regions
This change also allows us to remove RegionValue in favor of Long, if we can guarantee the memory pointed-to by the Long is valid when we access it.
We further propose that the consumer of an RDD passes a Region to the RDD. RDDs are, of course, permitted to create their own Regions and pass them to sub-computations. This creates a nested series of Region lifetimes much like properly matched parentheses.
Note that if an RDD transformation produces a new Region Value, it must place the Region Value in a region with lifetime longer than the transformation. The Region provided by the RDD consumer is always a valid place to put Region Values.
The practical effect of this is that instead of RDD[RegionValue] we instead have:
class ContextRDD[C, T: ClassTag](rdd: RDD[C => Iterator[T]]) {
ContextRDD supports all the usual RDD methods on an RDD[T], via this lifting method:
def withoutContext[U: ClassTag](f: Iterator[T] => Iterator[U])
: ContextRDD[C, U] =
new ContextRDD(rdd.map(_.andThen(f)))
For example, map(f: T => U):
def map[U: ClassTag](f: T => U): ContextRDD[C, U] =
withoutContext(_.map(f))
Instances of RDD[RegionValue] will be replaced with ContextRDD[RVDContext, Long]. (At first, RVDContext will have one field, a Region). Without a region, we cannot allocate any memory, so must users of ContextRDD will need to use the context-enhanced methods, like cmap:
private[this] def withContext[U: ClassTag](f: (C, Iterator[T]) => Iterator[U])
: ContextRDD[C, U] =
new ContextRDD(rdd.map(useCtx => ctx => f(ctx, useCtx(ctx))))
def cmap[U: ClassTag](f: (C, T) => U): ContextRDD[C, U] =
withContext((c, it) => it.map(f(c,_)))
}
For example, if the Longs in the RDD point to struct{a: int32} we could copy the a field:
def copyTheAField(c: RVDContext, s: Long): Long {
val r = c.region
val t = TStruct("a" -> TInt32())
r.appendInt(Memory.loadInt(t.loadField(t.fieldIdx("a"))))
}
NB: We don’t actually know into which region s points, but we can use Memory.loadInt to load from an arbitrary memory address.