Vector with memory from global storage (static duration)

[Frederick Gotham]

Is there anything wrong with the following code to create a vector that uses global memory?

Is there anything like this hidden in some corner of Boost?

#include <vector>
#include <cstddef>
#include <cstdint>
#include <new> /* Only for bad_alloc */

using std::vector;
using std::uint8_t;
using std::size_t;

template<typename T>
class MyAllocator {
public:
typedef T value_type;

protected:

static size_t const capacity = 4096;

static T buf[capacity];

public:

T *allocate(size_t n)
{
if (n > capacity)
throw std::bad_alloc();

return buf;
}

void deallocate(T *, size_t)
{
/* Do Nothing */
}
};

template<typename T>
T MyAllocator<T>::buf[MyAllocator<T>::capacity];


#include <iostream>
using std::cout;
using std::endl;

auto main(void) -> int
{
vector< uint8_t, MyAllocator<uint8_t> > v;

v.push_back('a');
v.push_back('a');
v.push_back('a');
v.push_back('a');

for (auto const &elem : v)
cout << elem << endl;
}

[Juha Nieminen]

Frederick Gotham <cauldwel...@gmail.com> wrote:
>
> Is there anything wrong with the following code to create
> a vector that uses global memory?

Yes. If you make more than one data container use it, they will
all be overwriting each other's data.

[Melzzzzz]

You can allocate only once....

--
press any key to continue or any other to quit...
U ničemu ja ne uživam kao u svom statusu INVALIDA -- Zli Zec
Na divljem zapadu i nije bilo tako puno nasilja, upravo zato jer su svi
bili naoruzani. -- Mladen Gogala

[James Kuyper]

The Allocator template argument of std::vector<> is supposed to meet the
allocator requirements listed in 20.5.3.5. MyAllocator<> fails to meet
the owverwhelming majority of those requirements. As far as I can see,
the only one it actually meets is the one for value_type.

It attempts, but fails, to meet the requirements for allocate() and
deallocate(), but there should be a flag indicating whether or not buf
has currently been allocated; allocate should check that flag, fail if
it's set, and otherwise set it. deallocate() should clear the flag.

Any one of the unmet requirements might cause your program to fail
catastrophically, though that's not guaranteed.

It's entirely feasible to meet those requirements with a class that
manages a fixed block of memory with static storage duration, and which
supports no more than a single allocation from that block - but this
isn't how you do it.

[Frederick Gotham]

On Saturday, October 19, 2019 at 11:02:50 PM UTC+1, James Kuyper wrote:

> It's entirely feasible to meet those requirements with a class that
> manages a fixed block of memory with static storage duration, and which
> supports no more than a single allocation from that block - but this
> isn't how you do it.

Surely there should be such a class template in Boost?

[James Kuyper]

I recommend asking that question in a forum devoted to Boost. My news
server doesn't know of any newsgroup whose name contains "Boost", but
there are apparently mailing lists:
<https://www.boost.org/community/groups.html>.

[Öö Tiib]

Boost has lot of allocator-related things but none seems anything like
what you do:
https://www.boost.org/doc/libs/1_71_0/doc/html/interprocess/allocators_containers.html

May I ask what is the usage for such odd allocator for unusual vector
(whose implementation is expecting allocators to meet requirements
to allocators that your example violates) instead of simply having
something like static std::array<uint8_t, 4096>?
Latter seems far more robust, more efficient in time and space and
also honest about what it really is.

[Frederick Gotham]

> > Surely there should be such a class template in Boost?
>
> I recommend asking that question in a forum devoted to Boost. My news
> server doesn't know of any newsgroup whose name contains "Boost", but
> there are apparently mailing lists:
> <https://www.boost.org/community/groups.html>.

I emailed the IT guy in my job just now to ask if he'll let me access the Gmane news server to get at those mailing lists.

[Juha Nieminen]

Öö Tiib <oot...@hot.ee> wrote:
> May I ask what is the usage for such odd allocator for unusual vector
> (whose implementation is expecting allocators to meet requirements
> to allocators that your example violates) instead of simply having
> something like static std::array<uint8_t, 4096>?
> Latter seems far more robust, more efficient in time and space and
> also honest about what it really is.

But it lacks the functionality of std::vector.

I have, in fact, oftentimes thought in the past that it could actually be
useful if there existed an allocator, usable with the standard library
containers, that allocated a fixed amount of space on the stack (ie.
just an in-built array which is used to allocate the memory).

If you temporarily need something like for example std::map inside
the scope of a function, for a relatively small amount of elements
(eg. in the hundreds of less), it would be enormously more efficient to
use an allocator like that instead of using the default allocator
(which is very slow because it uses ultimately the generic allocator
in libc, or whatever is the equivalent in a given OS).

[David Brown]

I believe there was an attempt to make a thing like a std::array but
where the size was determined at run-time, as a sort of C++ version of
C's variable length arrays. But it turned out to be rather difficult to
achieve because you can't make a function that makes a stack allocation.

[Öö Tiib]

On Tuesday, 22 October 2019 17:39:51 UTC+3, Juha Nieminen wrote:
> Öö Tiib <oot...@hot.ee> wrote:
> > May I ask what is the usage for such odd allocator for unusual vector
> > (whose implementation is expecting allocators to meet requirements
> > to allocators that your example violates) instead of simply having
> > something like static std::array<uint8_t, 4096>?
> > Latter seems far more robust, more efficient in time and space and
> > also honest about what it really is.
>
> But it lacks the functionality of std::vector.
>
> I have, in fact, oftentimes thought in the past that it could actually be
> useful if there existed an allocator, usable with the standard library
> containers, that allocated a fixed amount of space on the stack (ie.
> just an in-built array which is used to allocate the memory).

Something like that is present in boost.

The static_vector can grow only up to its fixed capacity:
<https://www.boost.org/doc/libs/1_71_0/doc/html/boost/container/static_vector.html>

The small_vector has also preallocated capacity in it but can
grow over that using an allocator:
<https://www.boost.org/doc/libs/1_71_0/doc/html/boost/container/small_vector.html>

> If you temporarily need something like for example std::map inside
> the scope of a function, for a relatively small amount of elements
> (eg. in the hundreds of less), it would be enormously more efficient to
> use an allocator like that instead of using the default allocator
> (which is very slow because it uses ultimately the generic allocator
> in libc, or whatever is the equivalent in a given OS).

When I needed temporary small sets then I used boost::intrusive::set
that leaves life-time management of elements up to user. So those
can be actually elements of array (or static_vector or the like).
For small maps I have used just sorted vectors of pairs.

[Chris M. Thomasson]

On 10/18/2019 3:20 AM, Frederick Gotham wrote:
>
> Is there anything wrong with the following code to create a vector that uses global memory?
>
> Is there anything like this hidden in some corner of Boost?

[...]

Fwiw, this reminds me of a simple region allocator I did in C:

https://groups.google.com/forum/#!original/comp.lang.c/7oaJFWKVCTw/sSWYU9BUS_QJ

[Soviet_Mario]

Il 21/10/19 16:34, Öö Tiib ha scritto:

> On Monday, 21 October 2019 10:23:10 UTC+3, Frederick Gotham wrote:
>> On Saturday, October 19, 2019 at 11:02:50 PM UTC+1, James Kuyper wrote:
>>
>>> It's entirely feasible to meet those requirements with a class that
>>> manages a fixed block of memory with static storage duration, and which
>>> supports no more than a single allocation from that block - but this
>>> isn't how you do it.
>>
>>
>> Surely there should be such a class template in Boost?
>
> Boost has lot of allocator-related things but none seems anything like
> what you do:
> https://www.boost.org/doc/libs/1_71_0/doc/html/interprocess/allocators_containers.html
>
> May I ask what is the usage for such odd allocator for unusual vector
> (whose implementation is expecting allocators to meet requirements
> to allocators that your example violates) instead of simply having
> something like static std::array<uint8_t, 4096>?

intresting example, which I would have misunderstood in most
context

I mean : I would have considered the class object (array
instance) itself to be static, but not (or not necessarily)
its content, which, if I'm not wrong again, does not
(necessarily) dwell inside the object

Instead it seems that the STATIC prefix makes the whole
object, both "helper" members and the main content (the
DATA) static as well.
Why so ?
I mean : the static clause is transitive and "propagates"
recursively to non-embedded sub-objects ?

It would be a handy feature, but I did not know it existed

> Latter seems far more robust, more efficient in time and space and
> also honest about what it really is.
>

--
1) Resistere, resistere, resistere.
2) Se tutti pagano le tasse, le tasse le pagano tutti
Soviet_Mario - (aka Gatto_Vizzato)

[Keith Thompson]

Soviet_Mario <Sovie...@CCCP.MIR> writes:
[...]

> intresting example, which I would have misunderstood in most
> context
>
> I mean : I would have considered the class object (array
> instance) itself to be static, but not (or not necessarily)
> its content, which, if I'm not wrong again, does not
> (necessarily) dwell inside the object
>
> Instead it seems that the STATIC prefix makes the whole
> object, both "helper" members and the main content (the
> DATA) static as well.
> Why so ?
> I mean : the static clause is transitive and "propagates"
> recursively to non-embedded sub-objects ?
>
> It would be a handy feature, but I did not know it existed

For a std::vector or std::string, for example, the contained data
is not part of the object itself. std::array is a bit unusual in
that the array elements *are* part of the std::array object, which
means that the elements will have the same storage duration as the
std::array object itself. (That's why the number of elements in
a std::array has to be known at compile time.)

A std::array object is essentially a structure with an array as
its only member.

You can see this by printing the value of `sizeof a`, where `a`
is a std::array object. For a vector, the size is going to be
a fixed value (which will vary depending on the implementation,
and *maybe*, but probably not, on the element type).

--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Will write code for food.
void Void(void) { Void(); } /* The recursive call of the void */

[Mr Flibble]

On 23/10/2019 23:15, Keith Thompson wrote:
> Soviet_Mario <Sovie...@CCCP.MIR> writes:
> [...]
>> intresting example, which I would have misunderstood in most
>> context
>>
>> I mean : I would have considered the class object (array
>> instance) itself to be static, but not (or not necessarily)
>> its content, which, if I'm not wrong again, does not
>> (necessarily) dwell inside the object
>>
>> Instead it seems that the STATIC prefix makes the whole
>> object, both "helper" members and the main content (the
>> DATA) static as well.
>> Why so ?
>> I mean : the static clause is transitive and "propagates"
>> recursively to non-embedded sub-objects ?
>>
>> It would be a handy feature, but I did not know it existed
>
> For a std::vector or std::string, for example, the contained data
> is not part of the object itself. std::array is a bit unusual in
> that the array elements *are* part of the std::array object, which
> means that the elements will have the same storage duration as the
> std::array object itself. (That's why the number of elements in
> a std::array has to be known at compile time.)

Wrong. std::string usually employs the "small string optimization" whereby
small strings are allocated within the object itself. I have also created
a "vecarray" container that does a similar thing for vectors.

/Flibble

--
"Snakes didn't evolve, instead talking snakes with legs changed into
snakes." - Rick C. Hodgin

“You won’t burn in hell. But be nice anyway.” – Ricky Gervais

“I see Atheists are fighting and killing each other again, over who
doesn’t believe in any God the most. Oh, no..wait.. that never happens.” –
Ricky Gervais

"Suppose it's all true, and you walk up to the pearly gates, and are
confronted by God," Bryne asked on his show The Meaning of Life. "What
will Stephen Fry say to him, her, or it?"
"I'd say, bone cancer in children? What's that about?" Fry replied.
"How dare you? How dare you create a world to which there is such misery
that is not our fault. It's not right, it's utterly, utterly evil."
"Why should I respect a capricious, mean-minded, stupid God who creates a
world that is so full of injustice and pain. That's what I would say."

[Juha Nieminen]

Öö Tiib <oot...@hot.ee> wrote:
>> I have, in fact, oftentimes thought in the past that it could actually be
>> useful if there existed an allocator, usable with the standard library
>> containers, that allocated a fixed amount of space on the stack (ie.
>> just an in-built array which is used to allocate the memory).
>
> Something like that is present in boost.
>
> The static_vector can grow only up to its fixed capacity:
> <https://www.boost.org/doc/libs/1_71_0/doc/html/boost/container/static_vector.html>
>
> The small_vector has also preallocated capacity in it but can
> grow over that using an allocator:
> <https://www.boost.org/doc/libs/1_71_0/doc/html/boost/container/small_vector.html>

I am talking about an allocator (usable with any standard library container),
not a std::vector replacement.

[Öö Tiib]

Yes you talk about concrete solution to problem that (I assume) is
low performance of using dynamic memory. The typical solutions
for reducing dynamic allocations (like using std::vector::reserve or std::unordered_set::reserve) are not good enough. So special
containers optimized to use dynamic storage management
provided by allocator not at all or very rarely are likely as good as
it can get. I don't think there can be special allocator that gives
same effect with stock containers.

[Soviet_Mario]

Il 24/10/19 00:15, Keith Thompson ha scritto:

> Soviet_Mario <Sovie...@CCCP.MIR> writes:
> [...]
>> intresting example, which I would have misunderstood in most
>> context
>>
>> I mean : I would have considered the class object (array
>> instance) itself to be static, but not (or not necessarily)
>> its content, which, if I'm not wrong again, does not
>> (necessarily) dwell inside the object
>>
>> Instead it seems that the STATIC prefix makes the whole
>> object, both "helper" members and the main content (the
>> DATA) static as well.
>> Why so ?
>> I mean : the static clause is transitive and "propagates"
>> recursively to non-embedded sub-objects ?
>>
>> It would be a handy feature, but I did not know it existed
>
> For a std::vector or std::string, for example, the contained data
> is not part of the object itself. std::array is a bit unusual in
> that the array elements *are* part of the std::array object, which
> means that the elements will have the same storage duration as the
> std::array object itself. (That's why the number of elements in
> a std::array has to be known at compile time.)

intresting. Actually I must admit I confused VECTOR for ARRAY :\

>
> A std::array object is essentially a structure with an array as
> its only member.

understood. Tnx

>
> You can see this by printing the value of `sizeof a`, where `a`
> is a std::array object. For a vector, the size is going to be
> a fixed value (which will vary depending on the implementation,
> and *maybe*, but probably not, on the element type).
>


--

[Soviet_Mario]

Il 24/10/19 01:19, Mr Flibble ha scritto:

uhm, strange ... it seems to me that such a solution may be
worse than the problem

I mean : 1) there is no a precise definition of SMALLness, a
known mandatory threshold to know in advance
2) is the optimization mandatory ? If not, even worser with
regard to the address (and storage type) of actual data.

we could fall in a scenario in which a small STATIC
std::string could have both the members and data static and
another instance not, just the members and data elsewhere,
without possibility to know in advance.


> /Flibble

[David Brown]

Yes. The ideal size of "smallness" will depend on many factors. But
some ground rules can be established. You will always need "metadata"
in the immediate part of the type - holding things like the current
count of items (vector elements, string bytes, etc.), a pointer to the
data part (typically on the heap), and the size of the allocated part.
On a 64-bit target, that would be 3 * 8 = 24 bytes. If the size of the
string, or the vector, is smaller than 24 bytes, then it makes sense to
store it locally within the object itself.

Whether you then say "24 bytes" is your "smallness", or pick something
else will depend on how you are using these types. A bigger "smallness"
will mean more wasted ram if your vectors/strings are not typically
"small" (or if they are typically very small). But heap allocated
memory usually has a minimum size anyway, and allocation on the stack is
very much faster than allocation on the heap. So you might pick a
"smallness" that gives a total object size of 64 bytes, for example - if
you keep the objects aligned they will match cache lines on many cpu's,
and it might even be possible to pass them around in large SIMD registers.

> 2) is the optimization mandatory ? If not, even worser with regard to
> the address (and storage type) of actual data.

That is up to the implementer of the classes. But "small string" or
"small data" optimisations are usually a win.

>
> we could fall in a scenario in which a small STATIC std::string could
> have both the members and data static and another instance not, just the
> members and data elsewhere, without possibility to know in advance.
>

Yes. So what?

[Paavo Helde]

What's the problem you are talking about?

Small string optimization is pretty much a perfect optimization as it
avoids dynamic allocation calls and provides better memory locality,
these are both a big deal nowadays. And having an optimization which
provides better performance in some situations is better than not having
an optimization at all.

> I mean : 1) there is no a precise definition of SMALLness, a known
> mandatory threshold to know in advance

What would you do with that knowledge? Shorten your strings? Smaller
strings are always faster to process, so if you could use smaller
strings in your code you would have already done that (assuming the
speed is so critical).

> 2) is the optimization mandatory ? If not, even worser with regard to
> the address (and storage type) of actual data.
>
> we could fall in a scenario in which a small STATIC std::string could
> have both the members and data static and another instance not, just the
> members and data elsewhere, without possibility to know in advance.

So what? If this happens, then presumably this comes from a shortening a
long string, meaning that the initial dynamic allocation call had
already happened and could not be anyway avoided any more.

[Paavo Helde]

On 24.10.2019 14:36, Soviet_Mario wrote:

> Il 24/10/19 01:19, Mr Flibble ha scritto:

>> Wrong. std::string usually employs the "small string optimization"
>> whereby small strings are allocated within the object itself.
>

> I mean : 1) there is no a precise definition of SMALLness, a known
> mandatory threshold to know in advance

The upper limit for "small string" length can be easily found out as
sizeof(std::string)-1 (-1 for the zero terminator byte, which can in
principle also serve as a marker that SSO is in use).

[Öö Tiib]

On Thursday, 24 October 2019 16:46:57 UTC+3, Paavo Helde wrote:
>
> The upper limit for "small string" length can be easily found out as
> sizeof(std::string)-1 (-1 for the zero terminator byte, which can in
> principle also serve as a marker that SSO is in use).

I think it is -2. Note that the std::string may contain zero bytes.
IOW ...:

std::string s("\0\0test", 6);

... has to work and after that ...

assert(s.length() == strlen(s.c_str()));

... does not hold. So one byte is needed for length of
short string and other is needed for zero terminator.

[Paavo Helde]

Right, thanks for the correction!

Storing the length separately would also mean that it's not needed to
calculate it as if by strlen() each time when needed (although strlen()
should also by very fast on such small strings).

[Bo Persson]

If you want to force it, you can store "unused space" instead of "size"
in the last byte. Then that byte happens to be zero when the space is
full. :-)

https://github.com/elliotgoodrich/SSO-23

For various reasons, like preferring an all-zero init being the empty
string, this is not used by the major implementations.


Bo Persson

[Soviet_Mario]

Il 24/10/19 14:25, David Brown ha scritto:

nothing particularly serious.
I was just considering that one could not always have the
full storage (lifetime) control they expect.
I tend to think too much in a C-like mindshape surely

[Paavo Helde]

On 24.10.2019 21:15, Soviet_Mario wrote:
> nothing particularly serious.
> I was just considering that one could not always have the full storage
> (lifetime) control they expect.
> I tend to think too much in a C-like mindshape surely

What makes you think that? Are you maybe afraid that any dynamically
allocated pieces in a static std::string object might somehow have
shorter lifetime than the std::string object itself? That cannot be,
this would ruin all invariants.

Or more probably, maybe you think that the lifetime of a static
std::string object has already begun before the program start, when it
maybe occupies some bytes in some data section of the executable on the
disk? No, it isn't, in C++ the lifetime of an object with a non-trivial
constructor begins when its initialization is complete. This only
happens at run-time.

[Keith Thompson]

That's *an* upper bound, not the least upper bound.

A std::string object has to store at least enough information to
determine whether it's using the small string optimization or not.

A quick experiment shows that sizeof (std::string) is 32 on Ubuntu
18.04, and it uses the small string optimization for lengths up to
15, so 16 of the 32 bytes can be used to hold the string value.
On some other systems (Cygwin, OpenBSD), sizeof (std::string) is
8 and the implementation doesn't appear to use the small string
optimization at all.

[Soviet_Mario]

Il 24/10/19 20:49, Paavo Helde ha scritto:

> On 24.10.2019 21:15, Soviet_Mario wrote:
>> nothing particularly serious.
>> I was just considering that one could not always have the
>> full storage
>> (lifetime) control they expect.
>> I tend to think too much in a C-like mindshape surely
>
> What makes you think that? Are you maybe afraid that any
> dynamically allocated pieces in a static std::string object
> might somehow have shorter lifetime than the std::string
> object itself? That cannot be, this would ruin all invariants.
>

almost

I was thinking slightly differently.
The requirements of a pure static object (not using malloc,
which is suitable only for fixed size arrays and strings,
not to dynamic ones) would be assessed at startup, that is
at the earliest stage of runtine, when the program is loading.
Either the static ram is enough and the program goes on to
never mind about any more, or not and it aborts.

Dynamically allocation may happen at any time during the
run, and it can fail to provide ram umpredictably. So we
would have a strange STATIC object without storage. I'm not
saying this would be a common scenario : just a violation of
the pact of the reserved ram in advance.

Now when one use the STATIC qualifier it might want more
than one effect, but one of them is just : being sure since
load that the ram requirements of a crucial object are
fulfilled or else to abort.

A static string entailing some dynamic allocation is strange
to me

> Or more probably, maybe you think that the lifetime of a
> static std::string object has already begun before the
> program start, when it maybe occupies some bytes in some
> data section of the executable on the disk?

yes sort of

> No, it isn't, in

ah ... I take note :\

> C++ the lifetime of an object with a non-trivial constructor
> begins when its initialization is complete. This only
> happens at run-time.

necessarily so, but ... HOW EARLY ?
I believed STATIC qualified objects were to be created at
LOADING of the program, not later, at least RAM would have
been reserved : it the actual data for initialization became
available later, then that ram would have been inited later,
but still just reserved.

If not the staticness seems to me rather faint :\

but ok, nice to learn things and change mind about my
misconceptions.

[Öö Tiib]

On Friday, 25 October 2019 10:50:09 UTC+3, Soviet_Mario wrote:
> Il 24/10/19 20:49, Paavo Helde ha scritto:
>

> > C++ the lifetime of an object with a non-trivial constructor
> > begins when its initialization is complete. This only
> > happens at run-time.
>
> necessarily so, but ... HOW EARLY ?
> I believed STATIC qualified objects were to be created at
> LOADING of the program, not later, at least RAM would have
> been reserved : it the actual data for initialization became
> available later, then that ram would have been inited later,
> but still just reserved.
>
> If not the staticness seems to me rather faint :\
>
> but ok, nice to learn things and change mind about my
> misconceptions.

The statics are initialized before running main in unspecified
order. That can cause famous fiasco that is also in FAQ:
<https://isocpp.org/wiki/faq/ctors#static-init-order>

Perhaps you find couple days to look over the whole FAQ,
C++ is *full* of "commonly misunderstood aspects" that
can pretty much work like bear traps.

[Soviet_Mario]

Il 25/10/19 13:18, Öö Tiib ha scritto:

I'm wandering among FAQs ... my God, how many situations of
danger I've never ever thought about ! :o