# FAST Extension proposal - MAP

**URL:** <https://forum.fixtrading.org/t/fast-extension-proposal-map/1014>\
**Category:** General Q&A\
**Tags:** xid\_169700, imported, fast-protocol\
**Created:** [September 28, 2008, 8:24am UTC](https://forum.fixtrading.org/t/fast-extension-proposal-map/1014 "2008-09-28T08:24:08Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![rolfandersson58\_x](https://avatars.discourse-cdn.com/v4/letter/r/b9e5f3/32.png) [@rolfandersson58\_x](https://forum.fixtrading.org/u/rolfandersson58_x)\
**Post date:** [September 28, 2008, 8:24am UTC](https://forum.fixtrading.org/t/fast-extension-proposal-map/1014/1 "2008-09-28T08:24:08Z")

</div>

Imported from previous forum

---

<div class="post-metadata">

**Author:** ![rolfandersson58\_x](https://avatars.discourse-cdn.com/v4/letter/r/b9e5f3/32.png) [@rolfandersson58\_x](https://forum.fixtrading.org/u/rolfandersson58_x)\
**Post date:** [September 28, 2008, 8:24am UTC](https://forum.fixtrading.org/t/fast-extension-proposal-map/1014/2 "2008-09-28T08:24:08Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![davidrosenborg30\_x](https://avatars.discourse-cdn.com/v4/letter/d/7ea924/32.png) [@davidrosenborg30\_x](https://forum.fixtrading.org/u/davidrosenborg30_x)\
**Post date:** [September 28, 2008, 9:23am UTC](https://forum.fixtrading.org/t/fast-extension-proposal-map/1014/3 "2008-09-28T09:23:32Z")

</div>

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. /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:  
> ||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

---

<div class="post-metadata">

**Author:** ![rolfandersson58\_x](https://avatars.discourse-cdn.com/v4/letter/r/b9e5f3/32.png) [@rolfandersson58\_x](https://forum.fixtrading.org/u/rolfandersson58_x)\
**Post date:** [September 28, 2008, 9:52am UTC](https://forum.fixtrading.org/t/fast-extension-proposal-map/1014/4 "2008-09-28T09:52:06Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![jacobnorthey\_x](https://yyz2.discourse-cdn.com/flex010/user_avatar/forum.fixtrading.org/jacobnorthey_x/32/61_2.png) [@jacobnorthey\_x](https://forum.fixtrading.org/u/jacobnorthey_x)\
**Post date:** [September 29, 2008, 3:34pm UTC](https://forum.fixtrading.org/t/fast-extension-proposal-map/1014/5 "2008-09-29T15:34:51Z")

</div>

My vote is for the following implementation

1. Map should not be able to combine with other operators
2. The presence bit should indicate reference or definition
3. Nullable fields should be encoded as a 0 presence bit and a zero reference

Example:

1. Defining a new value:

PBIT: 1  
ENCODING: 0x81 0x49 0x42 0xCD

Store the value “IBM” into cache index 1. Set field value to “IBM”

1. Referencing a value:

PBIT: 0  
ENCODING: 0x81

Set field value to cached value “IBM”

1. Sending a null value:

PBIT: 0  
ENCODING: 0x80

Set field value to null

---

<div class="post-metadata">

**Author:** ![rolfandersson58\_x](https://avatars.discourse-cdn.com/v4/letter/r/b9e5f3/32.png) [@rolfandersson58\_x](https://forum.fixtrading.org/u/rolfandersson58_x)\
**Post date:** [September 29, 2008, 5:42pm UTC](https://forum.fixtrading.org/t/fast-extension-proposal-map/1014/6 "2008-09-29T17:42:02Z")

</div>

using the pbit to distinguish between definition and reference has the following effects:

1. multiple pmap bits must be used to apply other operators
2. one pbit is used for each occurrence of a map field
3. 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
> 
> 1. Map should not be able to combine with other operators
> 2. The presence bit should indicate reference or definition
> 3. Nullable fields should be encoded as a 0 presence bit and a  
> zero reference
> 
> Example:
> 
> 1. Defining a new value:
> 
> PBIT: 1 ENCODING: 0x81 0x49 0x42 0xCD
> 
> Store the value “IBM” into cache index 1. Set field value to “IBM”
> 
> 1. Referencing a value:
> 
> PBIT: 0 ENCODING: 0x81
> 
> Set field value to cached value “IBM”
> 
> 1. Sending a null value:
> 
> PBIT: 0 ENCODING: 0x80
> 
> Set field value to null

---

<div class="post-metadata">

**Author:** ![rolfandersson58\_x](https://avatars.discourse-cdn.com/v4/letter/r/b9e5f3/32.png) [@rolfandersson58\_x](https://forum.fixtrading.org/u/rolfandersson58_x)\
**Post date:** [September 29, 2008, 5:50pm UTC](https://forum.fixtrading.org/t/fast-extension-proposal-map/1014/7 "2008-09-29T17:50:48Z")

</div>

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:
> 
> 1. multiple pmap bits must be used to apply other operators
> 2. one pbit is used for each occurrence of a map field
> 3. 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
> > 
> > 1. Map should not be able to combine with other operators
> > 2. The presence bit should indicate reference or definition
> > 3. Nullable fields should be encoded as a 0 presence bit and a zero  
> > reference
> > 
> > Example:
> > 
> > 1. Defining a new value:
> > 
> > PBIT: 1 ENCODING: 0x81 0x49 0x42 0xCD
> > 
> > Store the value “IBM” into cache index 1. Set field value to “IBM”
> > 
> > 1. Referencing a value:
> > 
> > PBIT: 0 ENCODING: 0x81
> > 
> > Set field value to cached value “IBM”
> > 
> > 1. Sending a null value:
> > 
> > PBIT: 0 ENCODING: 0x80
> > 
> > Set field value to null

---

<div class="post-metadata">

**Author:** ![jacobnorthey\_x](https://yyz2.discourse-cdn.com/flex010/user_avatar/forum.fixtrading.org/jacobnorthey_x/32/61_2.png) [@jacobnorthey\_x](https://forum.fixtrading.org/u/jacobnorthey_x)\
**Post date:** [September 29, 2008, 6:12pm UTC](https://forum.fixtrading.org/t/fast-extension-proposal-map/1014/8 "2008-09-29T18:12:28Z")

</div>

1. Treating the map as a standalone operator keeps the FAST specification simple.

2. The only operators that it would make sense to combine map with would be the delta or tail operators.

3. 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:
> > 
> > 1. multiple pmap bits must be used to apply other operators
> > 2. one pbit is used for each occurrence of a map field
> > 3. 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
> > > 
> > > 1. Map should not be able to combine with other operators
> > > 2. The presence bit should indicate reference or definition
> > > 3. Nullable fields should be encoded as a 0 presence bit and a zero  
> > > reference
> > > 
> > > Example:
> > > 
> > > 1. Defining a new value:
> > > 
> > > PBIT: 1 ENCODING: 0x81 0x49 0x42 0xCD
> > > 
> > > Store the value “IBM” into cache index 1. Set field value to “IBM”
> > > 
> > > 1. Referencing a value:
> > > 
> > > PBIT: 0 ENCODING: 0x81
> > > 
> > > Set field value to cached value “IBM”
> > > 
> > > 1. Sending a null value:
> > > 
> > > PBIT: 0 ENCODING: 0x80
> > > 
> > > Set field value to null

---

<div class="post-metadata">

**Author:** ![jacobnorthey\_x](https://yyz2.discourse-cdn.com/flex010/user_avatar/forum.fixtrading.org/jacobnorthey_x/32/61_2.png) [@jacobnorthey\_x](https://forum.fixtrading.org/u/jacobnorthey_x)\
**Post date:** [September 29, 2008, 6:22pm UTC](https://forum.fixtrading.org/t/fast-extension-proposal-map/1014/9 "2008-09-29T18:22:13Z")

</div>

> 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.

---

<div class="post-metadata">

**Author:** ![rolfandersson58\_x](https://avatars.discourse-cdn.com/v4/letter/r/b9e5f3/32.png) [@rolfandersson58\_x](https://forum.fixtrading.org/u/rolfandersson58_x)\
**Post date:** [September 29, 2008, 7:48pm UTC](https://forum.fixtrading.org/t/fast-extension-proposal-map/1014/10 "2008-09-29T19:48:16Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![craigrichards50\_x](https://avatars.discourse-cdn.com/v4/letter/c/d78d45/32.png) [@craigrichards50\_x](https://forum.fixtrading.org/u/craigrichards50_x)\
**Post date:** [September 29, 2008, 4:21pm UTC](https://forum.fixtrading.org/t/fast-extension-proposal-map/1014/11 "2008-09-29T16:21:02Z")

</div>

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. /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:  
> ||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

---

<div class="post-metadata">

**Author:** ![rolfandersson58\_x](https://avatars.discourse-cdn.com/v4/letter/r/b9e5f3/32.png) [@rolfandersson58\_x](https://forum.fixtrading.org/u/rolfandersson58_x)\
**Post date:** [September 29, 2008, 4:49pm UTC](https://forum.fixtrading.org/t/fast-extension-proposal-map/1014/12 "2008-09-29T16:49:18Z")

</div>

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
