[AFS3-std] Re: AFS-3 64-bit time I-D

[Andrew Deason]

On Fri, 11 Mar 2011 15:01:44 +0000
Simon Wilkinson <simon@sxw.org.uk> wrote:

> However, I'm less sure about the time resolution variable. This means
> that we are in effect tripling the size of every time payload in AFS.  

Also, addressing this specific concern about overhead...

I believe it is possible to pack the bits in more efficiently here, but
I didn't think it was worth the complexity (it's just 12 vs 8 bytes; I
didn't think we wanted to try that hard). I had thought of this before,
but didn't think it was worth pursuing:

When we have less resolution, obviously, some of the bits in the
timestamp field are unused, so the current proposal wastes some bits on
the wire. We can use those bits to communicate the resolution. Say we
define our time as 63-bits wide, 100ns. If we have actual 100ns
resolution, the representation is like this:

0XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

where the Xs are the time in 100ns, but the first bit is 0. If our
resolution is 200ns, the representation looks like this:

10XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

where the Xs are the time in 200ns, and we have 62 bits to represent it.
400ns would be

110XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

and we have 61 bits to represent the time. (Is there a name for
representation like this? It reminds of UTF-8, but I don't know if this
is called something more generally)

This limits how many different resolutions are representable (you can't
represent e.g. 300ns resolution), but I don't think that would be much
of a problem, since you're always within a factor of two.

This also has the problem that the resolution of 1-second is not
representable, since you can't double 100ns N times to get 1 second
evenly. This could be corrected by just making the base resolution 1/2^N
seconds or something, but it seems like that makes conversions to
existing time representations more annoying.

I dunno, I didn't really want to go this way, because I thought the
extra 4 bytes of overhead for the resolution field was worth the
simplicity in implementations. But I'm just mentioning it if someone
thinks it's a good idea.

-- 
Andrew Deason
adeason@sinenomine.net