Imported from previous forum
All,
this is the third of four proposals announced in a previous post.
Please review and comment.
/Rolf
EXTENSION PROPOSAL - MAP (table of {id, value} mappings)
Background
We have found (empirically in live feeds) that the "bit density"
of some fields is lower than optimum. These fields take one of
very few alternate values. As a consequence, the field value
could be represented with less than 7 bits, which is the minimum
field length in FAST for present values. The bit density could
be increased by allowing packing of multiple field values into
one SBIT-encoded field.
Introduction
A map is a table of values with corresponding identifiers:
{id, value}, {id, value}, … The id is a integer quantity
whereas the value may be numberic, string, or byte vector
in type. The idea is to replace a larger (size-wise) value
with a more compact id.
The map is shared between the sender and the receiver so
that the sender can define the {id, value} once and then
repeatedly refer to the value by sending the id.
Example
Let’s assume that you have a field where the value alternates
between a set of values. As an example, the values of Symbol
(tag 55) may be limited to a set of underlying security symbols.
The encoding af fields like symbol may be more space efficient
with a mechanism that allows an encoder to define and use a set
of values.
Wire representation
A MAP encoding will require additions to the wire format.
One alternative would be to add the following wire format:
A reference is encoded as a non-zero index
A definition is encoded as a zero followed by a non-zero index
and a value. A definition is at the same time a reference.
Abstract example of map wire representation:
|0|1|foo| => index=1 is defined as value=‘foo’
|1| => a reference to index 1 i.e. ‘foo’
|0|1|bar| => index=1 is redefined as value=‘bar’
(On a side-note, This format allows an encoder to choose between
different replacement algorithms (fifo, lru, …))
Template Syntax
The template syntax should probably be the other way around:
meaning that map would be used in the same way as other field operators.
Other things to consider is whether the map operator should utilize a bit in the presence map. If it should use a bit, there are a number of options.
Either we use the bit to indicate declaration (instead of using a special zero key), or we could combine the map operator with some other operator semantics.
In the latter case, the most straightforawd choice would probably be to add copy semantics. However, it might be a bit contradictory since if copy was a good candidate for the usage pattern in the first place, it could turn out that adding the map functionality was of little value.
/David
All,
this is the third of four proposals announced in a previous post. Please
review and comment. /RolfEXTENSION PROPOSAL - MAP (table of {id, value} mappings)
Background
We have found (empirically in live feeds) that the “bit density” of some
fields is lower than optimum. These fields take one of very few
alternate values. As a consequence, the field value could be represented
with less than 7 bits, which is the minimum field length in FAST for
present values. The bit density could be increased by allowing packing
of multiple field values into one SBIT-encoded field.Introduction
A map is a table of values with corresponding identifiers: {id, value},
{id, value}, … The id is a integer quantity whereas the value may be
numberic, string, or byte vector in type. The idea is to replace a
larger (size-wise) value with a more compact id.The map is shared between the sender and the receiver so that the sender
can define the {id, value} once and then repeatedly refer to the value
by sending the id.Example
Let’s assume that you have a field where the value alternates between a
set of values. As an example, the values of Symbol (tag 55) may be
limited to a set of underlying security symbols.The encoding af fields like symbol may be more space efficient with a
mechanism that allows an encoder to define and use a set of values.Wire representation
A MAP encoding will require additions to the wire format.
One alternative would be to add the following wire format:
A reference is encoded as a non-zero index A definition is encoded as a
zero followed by a non-zero index and a value. A definition is at the
same time a reference.Abstract example of map wire representation:
||1|foo| => index=1 is defined as value=‘foo’ 1| => a reference to
|index 1 i.e. ‘foo’ |1|bar| => index=1 is redefined as value=‘bar’(On a side-note, This format allows an encoder to choose between
different replacement algorithms (fifo, lru, …))Template Syntax
Maybe delta? Consider the following scenario.
You have 15000 ISIN-codes.
(index 1-127 => 1 byte, index 128-16383 => 2 bytes)
So, most of the time you will use 2 bytes to represent the index.
Now let’s assume some locality in the index values used.
Given that two values are within -64 – +63 apart, you would get
a one byte index delta instead of a two byte index value.
The back-side of this setup is that deltas <-8192 and >8191 will
need 3 bytes to be represented (because deltas are signed).
Anyway, we will most probably find use for the operators in the
map case as well.
/Rolf
The template syntax should probably be the other way around:
meaning that map would be used in the same way as other field operators.
Other things to consider is whether the map operator should
utilize a bit in the presence map. If it should use a bit, there
are a number of options.Either we use the bit to indicate declaration (instead of using a
special zero key), or we could combine the map operator with some
other operator semantics.In the latter case, the most straightforawd choice would probably
be to add copy semantics. However, it might be a bit contradictory
since if copy was a good candidate for the usage pattern in the
first place, it could turn out that adding the map functionality
was of little value./David
My vote is for the following implementation
- Map should not be able to combine with other operators
- The presence bit should indicate reference or definition
- Nullable fields should be encoded as a 0 presence bit and a zero reference
Example:
- Defining a new value:
PBIT: 1
ENCODING: 0x81 0x49 0x42 0xCD
Store the value “IBM” into cache index 1. Set field value to “IBM”
- Referencing a value:
PBIT: 0
ENCODING: 0x81
Set field value to cached value “IBM”
- Sending a null value:
PBIT: 0
ENCODING: 0x80
Set field value to null
using the pbit to distinguish between definition and reference has the following effects:
- multiple pmap bits must be used to apply other operators
- one pbit is used for each occurrence of a map field
- the wire representation of definitions will be one byte shorter
More than one pbit may be used by decimal fields.
The effect of 2 and 3 is that the one byte in 3 gets amortized over 8 reference occurrences of the field. Less than 8 references per definitions results in pmap being more compact, more than 8 references means leading zero byte results in definition being more compact.
(Nullability can be expressed for the by using a nullable representation for the first byte of both reference and definition)
/Rolf
My vote is for the following implementation
- Map should not be able to combine with other operators
- The presence bit should indicate reference or definition
- Nullable fields should be encoded as a 0 presence bit and a
zero referenceExample:
- Defining a new value:
PBIT: 1 ENCODING: 0x81 0x49 0x42 0xCD
Store the value “IBM” into cache index 1. Set field value to “IBM”
- Referencing a value:
PBIT: 0 ENCODING: 0x81
Set field value to cached value “IBM”
- Sending a null value:
PBIT: 0 ENCODING: 0x80
Set field value to null
sorry, I was a bit too quick posting …
why shouldn’t map combine with other operators?
/Rolf
using the pbit to distinguish between definition and reference has
the following effects:
- multiple pmap bits must be used to apply other operators
- one pbit is used for each occurrence of a map field
- the wire representation of definitions will be one byte shorter
More than one pbit may be used by decimal fields.
The effect of 2 and 3 is that the one byte in 3 gets amortized over
8 reference occurrences of the field. Less than 8 references per
definitions results in pmap being more compact, more than 8
references means leading zero byte results in definition being more
compact.(Nullability can be expressed for the by using a nullable
representation for the first byte of both reference and definition)/Rolf
My vote is for the following implementation
- Map should not be able to combine with other operators
- The presence bit should indicate reference or definition
- Nullable fields should be encoded as a 0 presence bit and a zero
referenceExample:
- Defining a new value:
PBIT: 1 ENCODING: 0x81 0x49 0x42 0xCD
Store the value “IBM” into cache index 1. Set field value to “IBM”
- Referencing a value:
PBIT: 0 ENCODING: 0x81
Set field value to cached value “IBM”
- Sending a null value:
PBIT: 0 ENCODING: 0x80
Set field value to null
-
Treating the map as a standalone operator keeps the FAST specification simple.
-
The only operators that it would make sense to combine map with would be the delta or tail operators.
-
Uses single presence map bit
sorry, I was a bit too quick posting …
why shouldn’t map combine with other operators?
/Rolf
using the pbit to distinguish between definition and reference has the
following effects:
- multiple pmap bits must be used to apply other operators
- one pbit is used for each occurrence of a map field
- the wire representation of definitions will be one byte shorter
More than one pbit may be used by decimal fields.
The effect of 2 and 3 is that the one byte in 3 gets amortized over 8
reference occurrences of the field. Less than 8 references per
definitions results in pmap being more compact, more than 8 references
means leading zero byte results in definition being more compact.(Nullability can be expressed for the by using a nullable
representation for the first byte of both reference and definition)/Rolf
My vote is for the following implementation
- Map should not be able to combine with other operators
- The presence bit should indicate reference or definition
- Nullable fields should be encoded as a 0 presence bit and a zero
referenceExample:
- Defining a new value:
PBIT: 1 ENCODING: 0x81 0x49 0x42 0xCD
Store the value “IBM” into cache index 1. Set field value to “IBM”
- Referencing a value:
PBIT: 0 ENCODING: 0x81
Set field value to cached value “IBM”
- Sending a null value:
PBIT: 0 ENCODING: 0x80
Set field value to null
The effect of 2 and 3 is that the one byte in 3 gets amortized over 8
reference occurrences of the field. Less than 8 references per
definitions results in pmap being more compact, more than 8 references
means leading zero byte results in definition being more compact.
Since FAST is a byte-level protocol, it is an all or nothing cost. Either using an additional presence bit increases the presence map size or it doesn’t. This is up to template designers to take into account.
TANSTAAFL, although it may be true for a specific template, the average the cost is one bit (and Murphy may skew this a bit). I.e. in 1 case out of 7 (not 8) you pay one byte. Not even a very good template designer will find the extra bit when he needs it 
The effect of 2 and 3 is that the one byte in 3 gets amortized over 8
reference occurrences of the field. Less than 8 references per
definitions results in pmap being more compact, more than 8 references
means leading zero byte results in definition being more compact.Since FAST is a byte-level protocol, it is an all or nothing cost.
Either using an additional presence bit increases the presence map size
or it doesn’t. This is up to template designers to take into account.
Would the map values be reset upon a dictionary reset? If not, at what point do they lose their meaning?
- Craig
All,
this is the third of four proposals announced in a previous post. Please
review and comment. /RolfEXTENSION PROPOSAL - MAP (table of {id, value} mappings)
Background
We have found (empirically in live feeds) that the “bit density” of some
fields is lower than optimum. These fields take one of very few
alternate values. As a consequence, the field value could be represented
with less than 7 bits, which is the minimum field length in FAST for
present values. The bit density could be increased by allowing packing
of multiple field values into one SBIT-encoded field.Introduction
A map is a table of values with corresponding identifiers: {id, value},
{id, value}, … The id is a integer quantity whereas the value may be
numberic, string, or byte vector in type. The idea is to replace a
larger (size-wise) value with a more compact id.The map is shared between the sender and the receiver so that the sender
can define the {id, value} once and then repeatedly refer to the value
by sending the id.Example
Let’s assume that you have a field where the value alternates between a
set of values. As an example, the values of Symbol (tag 55) may be
limited to a set of underlying security symbols.The encoding af fields like symbol may be more space efficient with a
mechanism that allows an encoder to define and use a set of values.Wire representation
A MAP encoding will require additions to the wire format.
One alternative would be to add the following wire format:
A reference is encoded as a non-zero index A definition is encoded as a
zero followed by a non-zero index and a value. A definition is at the
same time a reference.Abstract example of map wire representation:
||1|foo| => index=1 is defined as value=‘foo’ 1| => a reference to
|index 1 i.e. ‘foo’ |1|bar| => index=1 is redefined as value=‘bar’(On a side-note, This format allows an encoder to choose between
different replacement algorithms (fifo, lru, …))Template Syntax
the map values will be reset upon a dictionary reset
(otherwise the model for dictionaries would break)
/Rolf
Would the map values be reset upon a dictionary reset?
If not, at what point do they lose their meaning?
- Craig