Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #6578 > unrolled thread

std::set preallocate?

Back to article view | Back to comp.lang.c++

Contents

  std::set preallocate? Christopher <cpisz@austin.rr.com> - 2011-06-10 13:01 -0700
    Re: std::set preallocate? Pete Becker <pete@versatilecoding.com> - 2011-06-10 10:32 -1000
    Re: std::set preallocate? Edek <edek.pienkowski@gmail.com> - 2011-06-10 22:57 +0200
      Re: std::set preallocate? Christopher <cpisz@austin.rr.com> - 2011-06-10 14:51 -0700
        Re: std::set preallocate? Carlo Milanesi <carlo.nospam.milanesi@libero.it> - 2011-06-11 00:42 +0200
        Re: std::set preallocate? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2011-06-11 10:44 +0000
        Re: std::set preallocate? Edek <edek.pienkowski@gmail.com> - 2011-06-11 18:14 +0200
    Re: std::set preallocate? Juha Nieminen <nospam@thanks.invalid> - 2011-06-11 04:52 +0000

#6578 — std::set preallocate?

Got a complaint that allocation is costly for 2000 items to be
inserted into a set one by one. I need to preallocate, and depend on
the set growing, if needed, after the number of items exceeds the
preallocation.

Do I do so like this?

class A
{
public:
   A()
   {
       m_values.get_allocator.allocate(2000);
   }
   ~A()
   {
      // Does set still clean up after itself?
   }

   typedef std::pair<unsigned, std::smart_ptr> Value;
   typedef std::set<Value> Values;
   Values m_values;
}

[toc] | [next] | [standalone]

#6585

On 2011-06-10 10:01:02 -1000, Christopher said:

> Got a complaint that allocation is costly for 2000 items to be
> inserted into a set one by one. I need to preallocate, and depend on
> the set growing, if needed, after the number of items exceeds the
> preallocation.

Sets typically use a separate data block for each element, so 
allocating a bunch of blocks up front doesn't really accomplish 
anything. It's not like a vector, which uses a single data block and 
has to resize that block as elements are added.

> 
> Do I do so like this?

No, definitely not.

> 
> class A
> {
> public:
>    A()
>    {
>        m_values.get_allocator.allocate(2000);

This allocates a data block that can hold 2000 elements and throws away 
its address.

-- 
  Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The 
Standard C++ Library Extensions: a Tutorial and Reference 
(www.petebecker.com/tr1book)

[toc] | [prev] | [next] | [standalone]

#6586

On 06/10/2011 10:01 PM, Christopher wrote:
> Got a complaint that allocation is costly for 2000 items to be
> inserted into a set one by one. I need to preallocate, and depend on
> the set growing, if needed, after the number of items exceeds the
> preallocation.
>
> Do I do so like this?
>
> class A
> {
> public:
>     A()
>     {
>         m_values.get_allocator.allocate(2000);
>     }
>     ~A()
>     {
>        // Does set still clean up after itself?
>     }
>
>     typedef std::pair<unsigned, std::smart_ptr>  Value;
>     typedef std::set<Value>  Values;
>     Values m_values;
> }

No, not really. Allocators have something called 'rebind'.
Basically a set gets an allocator of T, and rebinds it to allocator
of its own internal type to carry its [meta]data.

Since these are templates, the two allocators differ in c++ type.

If you think you can outdo the standard allocators, you need to
invest into allocator requirements first, to get the formalities right;
then you need to make your allocator perform well. Take a look
at new_allocator (simple allocator just calling ::new).

Maybe there are other ways, but if you know the characteristics
of this set's usage, e.g. a set will contain 2000 elements,
then they will be mainly constant in size, you could optimise by 
preallocating. Or preallocating in chunks as needed.
It's just a bit too hairy templated stuff to do so for no reason,
and not so easy to get a really good performance out of it.
Explore first; [1] is a rather easy way to start.

BTW, do you need a set? Maybe a hashset? Maybe a vector?

Edek

[1] http://www.boost.org/doc/libs/1_44_0/libs/pool/doc/interfaces.html

[toc] | [prev] | [next] | [standalone]

#6592

On Jun 10, 3:57 pm, Edek <edek.pienkow...@gmail.com> wrote:
> On 06/10/2011 10:01 PM, Christopher wrote:
>
>
>
>
>
> > Got a complaint that allocation is costly for 2000 items to be
> > inserted into a set one by one. I need to preallocate, and depend on
> > the set growing, if needed, after the number of items exceeds the
> > preallocation.
>
> > Do I do so like this?
>
> > class A
> > {
> > public:
> >     A()
> >     {
> >         m_values.get_allocator.allocate(2000);
> >     }
> >     ~A()
> >     {
> >        // Does set still clean up after itself?
> >     }
>
> >     typedef std::pair<unsigned, std::smart_ptr>  Value;
> >     typedef std::set<Value>  Values;
> >     Values m_values;
> > }
>
> No, not really. Allocators have something called 'rebind'.
> Basically a set gets an allocator of T, and rebinds it to allocator
> of its own internal type to carry its [meta]data.
>
> Since these are templates, the two allocators differ in c++ type.
>
> If you think you can outdo the standard allocators, you need to
> invest into allocator requirements first, to get the formalities right;
> then you need to make your allocator perform well. Take a look
> at new_allocator (simple allocator just calling ::new).
>
> Maybe there are other ways, but if you know the characteristics
> of this set's usage, e.g. a set will contain 2000 elements,
> then they will be mainly constant in size, you could optimise by
> preallocating. Or preallocating in chunks as needed.
> It's just a bit too hairy templated stuff to do so for no reason,
> and not so easy to get a really good performance out of it.
> Explore first; [1] is a rather easy way to start.
>
> BTW, do you need a set? Maybe a hashset? Maybe a vector?
>
> Edek
>
> [1]http://www.boost.org/doc/libs/1_44_0/libs/pool/doc/interfaces.html- Hide quoted text -
>
> - Show quoted text -


Container needs to act like a queue more or less. I fill it with items
that I need to do operations on, do the operations, then erase them
from the container. However, the container has to guarentee that the
items are unique. Because the methods where they are used may receive
the same items multiple times before the time comes around to do the
operations on them.

So, I need some kind of container that is a queue of unique items.

[toc] | [prev] | [next] | [standalone]

#6594

On 10/06/2011 23.51, Christopher wrote:
>>> Got a complaint that allocation is costly for 2000 items to be
>>> inserted into a set one by one. I need to preallocate, and depend on
>>> the set growing, if needed, after the number of items exceeds the
>>> preallocation.
>
> Container needs to act like a queue more or less. I fill it with items
> that I need to do operations on, do the operations, then erase them
> from the container. However, the container has to guarentee that the
> items are unique. Because the methods where they are used may receive
> the same items multiple times before the time comes around to do the
> operations on them.
>
> So, I need some kind of container that is a queue of unique items.

You could define your own container as a wrapper of a couple of 
containers: a deque and an unordered_set (part of C++0x, but already 
available from some sources, perhaps as "hash_set").
Your "push_back" function checks if the item is contained in the 
unordered_set, and if it is not already contained, it inserts it both in 
the deque and in the unordered_set.
Your "pop_front" function gets the next item from the deque, and then 
removes it from both the deque and the unordered_set.
Variants are:
- Use a vector instead of a deque.
- Store in the unordered_set only a (optionally computed) search key.
- If the search key is an integer having a small range, use a vector 
instead of an unordered_set, with as many items as the values in the 
range of the search key.
- Preallocate the unordered_set using "reserve".
- If you use one or more vectors, preallocate such vectors using "reserve".

-- 

Carlo Milanesi
http://carlomilanesi.wordpress.com/

[toc] | [prev] | [next] | [standalone]

#6613

On Fri, 2011-06-10, Christopher wrote:
> On Jun 10, 3:57 pm, Edek <edek.pienkow...@gmail.com> wrote:
>> On 06/10/2011 10:01 PM, Christopher wrote:
>> > Got a complaint that allocation is costly for 2000 items to be
>> > inserted into a set one by one. I need to preallocate, and depend on
>> > the set growing, if needed, after the number of items exceeds the
>> > preallocation.
>>
...

>> BTW, do you need a set? Maybe a hashset? Maybe a vector?
...
>
> Container needs to act like a queue more or less. I fill it with items
> that I need to do operations on, do the operations, then erase them
> from the container. However, the container has to guarentee that the
> items are unique. Because the methods where they are used may receive
> the same items multiple times before the time comes around to do the
> operations on them.
>
> So, I need some kind of container that is a queue of unique items.

I haven't thought this through, but take a look at std::make_heap()
and friends. They are easy to overlook because they're not containers.

/Jorgen

-- 
  // Jorgen Grahn <grahn@  Oo  o.   .  .
\X/     snipabacken.se>   O  o   .

[toc] | [prev] | [next] | [standalone]

#6621

>> BTW, do you need a set? Maybe a hashset? Maybe a vector?
>>
>> Edek

> Container needs to act like a queue more or less. I fill it with items
> that I need to do operations on, do the operations, then erase them
> from the container. However, the container has to guarentee that the
> items are unique. Because the methods where they are used may receive
> the same items multiple times before the time comes around to do the
> operations on them.
>
> So, I need some kind of container that is a queue of unique items.

There are some improvisations possible. Like, on plain vectors,

1) store the 'queue' as a vector
2) store incoming items in a separate vector (unsorted, with duplicates)
3) when you need to fetch some,
    a) merge vectors, sort, remove duplicates by remove_copy_if
    b) take some (and do operations on them)
    c) create a new separate vector for point 2

This is just from the top of my head as an example. It
will not fit every scenario (or maybe even any ;) )

a + b could be like:

struct DuplicateRemover
{
     last = someComparingAsFalse;

     bool operator () (next) {
        if (next == last) return true;

        last = next;

        return false;
    }
}

struct FirstN {
      FirstN (int n , iterator toHandle, iterator toStore)
    ... fields init, count=0 {}

      void operator () (next) {
          if (count ++ < n )
              put next in toHandle
          else
              put next in toStore
      }
}

copy (incoming.begin(), incoming.end(), merge.end());

... sort merge ...

remove_copy_if (merge.begin(), merge.end (),
        make_function_output_iterator(
              FirstN (100, toHandleVector.begin(), new_store.begin()),
	DuplicateRemover());

throw out merge, new_store is left items, handle the toHandle...

As you see, there is a lot of copying and comparing involved,
so maybe this is a not so good idea, if the 'set' is huge
and you only take a couple of items very often.

But you certainly can preallocate.

Edek

[toc] | [prev] | [next] | [standalone]

#6606

Christopher <cpisz@austin.rr.com> wrote:
> Got a complaint that allocation is costly for 2000 items to be
> inserted into a set one by one. I need to preallocate, and depend on
> the set growing, if needed, after the number of items exceeds the
> preallocation.

  std::set does not support reserving memory. If you want that, you need 
to use some specialized allocator that does exactly that. For example this 
one does that: http://warp.povusers.org/FSBAllocator/

>       m_values.get_allocator.allocate(2000);

  That accomplishes nothing but to irreversibly leak a big bunch of 
memory.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c++

csiph-web