Placement new

[thekashyap]

Hi Guys,
I was just reading up Lippman to learn more C++ and came across the third syntax of new operator called "placement new".
I have a specific problem where I thot I'll use it, but it turns out to be a total fiasco. :).
My requirement is: I need to create lots and lots of pixel objects (e.g. about 100 matrixs of 800x800 pixels each). So I thot I'll use placement new to pre-allocated memory (line 16) and use it so it'll save time.
But placement new is just returning the address of buffer every time I call it.

Is there something wrong in way I'm using it? or is it that placement new can't be used for my problem and I have to write my own new/delete?

class pixel
{
public:
    pixel( ) : _i(0)
    {}

    void print() { cout << _i << endl ; }

    int _i ;
};

//main program to call the array for 4 ints and return average
int main()
{
    static const int MAX_PIXELS = 10 ;
    int* buffer = new int[MAX_PIXELS] ;
    vector<int*> v ;
    for( int i = 0; i < MAX_PIXELS; i++ )
    {
        int* p = new (buffer) int() ;
        *p = i ;

        v.push_back( p ) ;
        cout << "p = " << p << ", *p = " << *p << endl ;
    }

    cout << endl << "-------printing-------" << endl << endl ;

    for( i = 0; i < v.size(); i++ )
    {
        cout << "v[i] = " << v[i] << ", *v[i] = " << *v[i] << endl ;
    }
    return 0 ;
}

Output:
p = 002F07A8, *p = 0
p = 002F07A8, *p = 1
p = 002F07A8, *p = 2
p = 002F07A8, *p = 3
p = 002F07A8, *p = 4
p = 002F07A8, *p = 5
p = 002F07A8, *p = 6
p = 002F07A8, *p = 7
p = 002F07A8, *p = 8
p = 002F07A8, *p = 9

-------printing-------

v = 002F07A8, *v = 9
v = 002F07A8, *v = 9
v = 002F07A8, *v = 9
v = 002F07A8, *v = 9
v = 002F07A8, *v = 9
v = 002F07A8, *v = 9
v = 002F07A8, *v = 9
v = 002F07A8, *v = 9
v = 002F07A8, *v = 9
v = 002F07A8, *v = 9
Press any key to continue

[vijayan121]

placement new is used when you do not want operator new to allocate memory (you have pre-allocated it and you want to place the object there), but you do want the object to be constructed. examples of typical situations where this may be required are
a. you want to create objects in memory shared between two different processes
b. you want objects to be created in non-pageable memory
c. you want to seperate memory allocation from construction eg. in implementing a std::vector<> (see std::vector<>::reserve)

the basic problem is that the constructor is a peculiar function; when it starts off, there is no object, only raw memory. and by the time it finishes, you have a fully initialized object. therefore i. the constructor cannot be called on an object ii. however, it needs to access (and initialize) non-static members. this makes calling the constructor directly an error. the solution is the placement form of operator new.

this operator is implemented as

inline void* operator new( size_t sz, void* here ) 
{ return here ; }
inline void* operator new[]( size_t sz, void* here ) 
{ return here ; }

in your case, using this is not required as an int is pod, it has a trivial constructor. if you want to use it, you could use it this way:

for( int i = 0; i < MAX_PIXELS; i++ )
    {
        int* p = new (buffer+i) int(i) ; // specify where you want the object
        v.push_back( p ) ;
        cout << "p = " << p << ", *p = " << *p << endl ;
    }

note: do not call delete for objects allocated using placement new. if they have non-trivial destructors, call the destructor directly (destruction is an operation on an object and therefore can be called!). and release the memory you allocated yourself.

[vijayan121]

My requirement is: I need to create lots and lots of pixel objects (e.g. about 100 matrixs of 800x800 pixels each)

this is the kind of problem where you could use the flyweight design pattern quite effectively. see:
Design Patterns: Elements of Reusable Object-Oriented Software
by Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides (aka Gang of Four) - Addison-Wesley Professional Computing Series pages 195-206.
if you do not have ready access to the book, here is a lik which may help you:
http://www.informit.com/articles/article.asp?p=468380&seqNum=1&rl=1

[thekashyap]

Thanks.

A few things:
1. The code I posted was a li'l wrong. I meant to create objects of pixel class rather than int. Here is the updated one:

class pixel
{
public:
    pixel( ) : _x(0), _y(0) {}

    void print() { cout << this << " = " << _x << ',' << _y << endl ; }

    int _x, _y ;
};

int main()
{
    static const int MAX_PIXELS = 10 ;
    pixel* buffer = new pixel[MAX_PIXELS] ;
    vector<pixel*> v ;
    for( int i = 0; i < MAX_PIXELS; i++ )
    {
        pixel* p = new (buffer) pixel() ;
        p->_x = i ;
        p->_y = MAX_PIXELS - i ;
        p->print() ;

        v.push_back( p ) ;
    }

    cout << endl << "-------printing-------" << endl << endl ;

    for( int j = 0; j < v.size(); j++ )
    { cout << "v[" << j << "] = " ; v[j]->print() ; }

    return 0 ;
}

Output is on similar lines:
----------------------------------------------
002F07A8 = 0,10
002F07A8 = 1,9
002F07A8 = 2,8
002F07A8 = 3,7
002F07A8 = 4,6
002F07A8 = 5,5
002F07A8 = 6,4
002F07A8 = 7,3
002F07A8 = 8,2
002F07A8 = 9,1

-------printing-------

v[0] = 002F07A8 = 9,1
v[1] = 002F07A8 = 9,1
v[2] = 002F07A8 = 9,1
v[3] = 002F07A8 = 9,1
v[4] = 002F07A8 = 9,1
v[5] = 002F07A8 = 9,1
v[6] = 002F07A8 = 9,1
v[7] = 002F07A8 = 9,1
v[8] = 002F07A8 = 9,1
v[9] = 002F07A8 = 9,1
Press any key to continue
----------------------------------------------

2. I had a cursory look at the link you've posted and wikipedia. I think it is trying to optimize the amount of memory allocations rather than performance of each memory allocation. But I learned a new pattern. :).
In my usecase, there are no practical memory constraints, we have 2-3GB of RAM available for my program. The more important aspect is to ensure good performance. Also in my case, one pixel obj doesn't have anything common with any other pixel obj (so can't use fly weight to reduce the size of each pixel).
Also in I need all 800x800 pixel objects to exist in memory at the same time as I process them together.

Anyway, from the description you gave (of placement new) I feel I can't use it for my purpose. Instead I will have to implement my own new/delete to optimize the allocation. Do get back if you have any further comments.

[vijayan121]

placement new can still be used; it would be more efficient in terms of both time and space than using the normal new.
here is the code (with the placement new modified).

#include <iostream>
#include <vector>
#include <new>
using namespace std ;

class pixel
{
  public:
    pixel( ) : _x(0), _y(0) {}
    void print() { cout << this << " = " << _x << ',' << _y << endl ; }
    int _x, _y ;
};

int main()
{
  static const int MAX_PIXELS = 10 ;
  pixel* buffer = new pixel[MAX_PIXELS] ;
  vector<pixel*> v ;
  for( int i = 0; i < MAX_PIXELS; i++ )
  {
      pixel* p = new (buffer+i) pixel() ; // buffer => buffer+i
      p->_x = i ;
      p->_y = MAX_PIXELS - i ;
      p->print() ;
      v.push_back( p ) ;
  }
  cout << endl << "-------printing-------" << endl << endl ;
  for( vector<pixel*>::size_type j = 0; j < v.size(); j++ )
  { cout << "v[" << j << "] = " ; v[j]->print() ; }
  return 0 ;
}

and here is the output:
0x804c000 = 0,10
0x804c008 = 1,9
0x804c010 = 2,8
0x804c018 = 3,7
0x804c020 = 4,6
0x804c028 = 5,5
0x804c030 = 6,4
0x804c038 = 7,3
0x804c040 = 8,2
0x804c048 = 9,1

-------printing-------

v[0] = 0x804c000 = 0,10
v[1] = 0x804c008 = 1,9
v[2] = 0x804c010 = 2,8
v[3] = 0x804c018 = 3,7
v[4] = 0x804c020 = 4,6
v[5] = 0x804c028 = 5,5
v[6] = 0x804c030 = 6,4
v[7] = 0x804c038 = 7,3
v[8] = 0x804c040 = 8,2
v[9] = 0x804c048 = 9,1

note: you were giving the same address (buffer) for every pixel!

[vijayan121]

from your posted code, i infer/guess that the following are true:
a. you know the number of pixels before hand
b. you do not need to destroy pixels till end of program.
c. you want to keep the pixels in a std::vector.
and as stated, your goal is to increase the allocation/access speed.
it would be more efficient to use a std::vector<pixel> instead of a std::vector<pixel*> (extra spae requirement for pointer, two memory accesses instead of one). and if you need the address of a pixel for some reason, &(v) is always available.
for fast allocation, and for using a vector with value semantics, the easiest way is to use a custom allocater. here is some sample code:

#include <iostream>
#include <vector>
#include <new>
#include <memory>
using namespace std ;

class pixel
{
  public:
    pixel( int xx=0, int yy=0 ) : _x(xx), _y(yy) {}
    void print() { cout << this << " = " << _x << ',' << _y << endl ; }
    int _x, _y ;
};

struct pixel_allocator : public std::allocator<pixel>
{
    enum { NUM_PIXELS = 1024*1024*32 }; // number of pixels
    pointer allocate( size_type N, const void* = 0 ) 
    { 
        void* pv = cnt<NUM_PIXELS ? buffer + cnt*sizeof(pixel) : 0 ; 
        cnt += N ; 
        return pointer(pv) ; 
    } 
    void deallocate( pointer ptr, size_type count ) {} // do nothing!
    void construct( pointer ptr, const pixel& val ) { new(ptr) pixel(val) ; }
    void destroy( pointer ptr ) { ptr->pixel::~pixel() ; }
    size_type max_size() const throw() { return NUM_PIXELS ; }
    static size_type cnt ; // number of pixels so far allocated
    static char* buffer ; // pointer to pre-allocated memory
};

pixel_allocator::size_type pixel_allocator::cnt = 0 ;
char* pixel_allocator::buffer = 
                       new char[ pixel_allocator::NUM_PIXELS * sizeof(pixel) ] ;

int main()
{
  static const int MAX_PIXELS = 10 ;
  vector<pixel,pixel_allocator> v ;
  for( int i = 0; i < MAX_PIXELS; i++ )
      v.push_back( pixel( i, MAX_PIXELS - i ) ) ;
  for( vector<pixel>::size_type j = 0; j < v.size(); j++ )
  { cout << "v[" << j << "] = " ; v[j].print() ; }
  return 0 ;
}

output:
g++ -Wall -std=c++98 pixels.c ; ./a.out
v[0] = 0x804c078 = 0,10
v[1] = 0x804c080 = 1,9
v[2] = 0x804c088 = 2,8
v[3] = 0x804c090 = 3,7
v[4] = 0x804c098 = 4,6
v[5] = 0x804c0a0 = 5,5
v[6] = 0x804c0a8 = 6,4
v[7] = 0x804c0b0 = 7,3
v[8] = 0x804c0b8 = 8,2
v[9] = 0x804c0c0 = 9,1

note: as i have not defined rebind, this allocator needs to be augmented if you want to use it with a list. it is just sufficient to make it work on a simple vector or deque.

[thekashyap]

Thanks that's really helpful.. :)

Before I answer a few things, may be this will help understand.
Each matrix I talked abt corresponds to coverage area of a GSM transmitter/BTS and each pixel in that area is a 5-5 meters or square and power received from the transmitter is the basic property of each pixel.
There is one binary file per transmitter that contains all pixels of a transmitter (number of pixels would vary) We read these files and create matrices.
----------
a. you know the number of pixels before hand
>> Just before starting allocation for each matrix, but it differs from matrix to matrix. But I'm sure I can adjust the code accordingly.

b. you do not need to destroy pixels till end of program.
>> No, there are cases

c. you want to keep the pixels in a std::vector.
>> No, the actual container is a simple C-style array of type pixel**. But I'm sure I can adjust the code accordingly.

it would be more efficient to use a std::vector<pixel> instead of a std::vector<pixel*> (extra space requirement for pointer, two memory accesses instead of one).
>> But I thot vector (or other STL containers map/set/deque..) call copy c'tor on insert/push_back, so wouldn't it increase the overall time taken if I use pixel instead of pixel* ?
That would surely happen in my case where I use a C-style array.

[vijayan121]

i think the best way would be
a. allocate an array of pixel* , one entry per transmitter.

pixel** ppp = new pixel* [ NUM_TRANSMITTERS ] ;

b. as you read each file, allocate memory for the pixels

ppp[transmitter_number] = new pixel[npixels_in_this_transmitter] ;

c. you could either read the file data directly into the array, or you could create a local variable of type pixel and copy it into the array. do not worry about the overhead of copying the pixel object; it is small (x,y,power) and can be copied using bit-wise semantics (in c++ jargon, has a trivial copy constructor). so the compiler will generate the copy code inline (three or four instructions for your pixel).
d. need a little more information about destroying pixels. do you destroy pixels one by one or is it that when a new file comes in, you destroy all the pixels for that transmitter and create a new set of pixels? and if it is the second case, would the number of pixels change?