Linearly Value Compressed Vector (Container)

[=?iso-8859-1?B?Tm9yZGz2dw==?=]

Hey there, C++ Coders.

Does anyone know of a C++ (template) (vector) container that packs its
elements based on their relative minimum and maximum value (offset and
span) and (minimum) stride.

Example:
The pointers [ 0x00, 0x04, 0x12, 0x20 ] when packed should be stored
internally in the template<T> container as
T min: 0
T stride: 4
packed values: [ 0, 1, 3, 5 ] (in this case be stored in a
std::vector<uint8_t>)

I think such a container would be especially suitable for storing
"small" arrays of pointers. Especially on a 64-bit architecture where
a pointer takes 8 bytes, this would reduce memory usage by up to 8
times. This example, of course, holds only for the ideal case where
the array has exactly 256 number of elements and these elements are
all aligment on a linear grid with equal spacing (stride).

This template would also work great for elements having integer types.


Many thanks in advance,

Nordlöw

 

[Alf P. Steinbach]

* Nordlöw:

Hey there, C++ Coders.

Does anyone know of a C++ (template) (vector) container that packs its
elements based on their relative minimum and maximum value (offset and
span) and (minimum) stride.

Example:
The pointers [ 0x00, 0x04, 0x12, 0x20 ] when packed should be stored
internally in the template<T> container as
T min: 0
T stride: 4
packed values: [ 0, 1, 3, 5 ] (in this case be stored in a
std::vector<uint8_t>)

I think such a container would be especially suitable for storing
"small" arrays of pointers. Especially on a 64-bit architecture where
a pointer takes 8 bytes, this would reduce memory usage by up to 8
times. This example, of course, holds only for the ideal case where
the array has exactly 256 number of elements and these elements are
all aligment on a linear grid with equal spacing (stride).

This template would also work great for elements having integer types.

In order for this to be useful for pointers, the pointers need to be
very closely equal, i.e. point into the same array and structure.

In that case why not just store indices, plus a base address pointer?

What you call the "stride" is handled automatically by the C++ type
machinery, if you just let it (e.g. int *p yields stride sizeof(int)).

 

[Victor Bazarov]

Does anyone know of a C++ (template) (vector) container that packs its
elements based on their relative minimum and maximum value (offset and
span) and (minimum) stride.

Example:
The pointers [ 0x00, 0x04, 0x12, 0x20 ] when packed should be stored
internally in the template<T> container as
T min: 0
T stride: 4
packed values: [ 0, 1, 3, 5 ] (in this case be stored in a
std::vector<uint8_t>)

I think such a container would be especially suitable for storing
"small" arrays of pointers. Especially on a 64-bit architecture where
a pointer takes 8 bytes, this would reduce memory usage by up to 8
times. This example, of course, holds only for the ideal case where
the array has exactly 256 number of elements and these elements are
all aligment on a linear grid with equal spacing (stride).

This template would also work great for elements having integer types.

Looks interesting. No, I've not seen, nor have I had any need to
implement, anything like that. To be entirely honest, sorting a list
(vector, set) of pointers based on pointer values is not a critical
task. Sorting a container of pointers based on the object values is
done frequently, but I am not sure how what you showed would help.

I am thinking of a container with indexing into another container, which
I've seen the need for, but sorting that one would still be done on some
kind of predicate not directly related to the pointer values, so, again,
only space savings have meaning.

Or, maybe I've misunderstood something...

V

 

[=?ISO-8859-1?Q?Erik_Wikstr=F6m?=]

Hey there, C++ Coders.

Does anyone know of a C++ (template) (vector) container that packs its
elements based on their relative minimum and maximum value (offset and
span) and (minimum) stride.

Example:
The pointers [ 0x00, 0x04, 0x12, 0x20 ] when packed should be stored
internally in the template<T> container as
T min: 0
T stride: 4
packed values: [ 0, 1, 3, 5 ] (in this case be stored in a
std::vector<uint8_t>)

I think such a container would be especially suitable for storing
"small" arrays of pointers. Especially on a 64-bit architecture where
a pointer takes 8 bytes, this would reduce memory usage by up to 8
times. This example, of course, holds only for the ideal case where
the array has exactly 256 number of elements and these elements are
all aligment on a linear grid with equal spacing (stride).

There's always the risk that such a scheme for pointers would result in
slower code due to the need to create a real pointer from the smaller
one you stored and then dereferencing it. Besides, if you have 64 bit
address space you probably also have physical memory enough that other
optimisations are more worthwhile.