Can I avoid the use of arrays in this situation or do I have to usethem?

[mike3]

Actually, for this implementation you don't need to
push any buffers at all initially. You just need
to pop and then push when you've done. If the under-
lying buffer is empty a new vector would be created
automatically (the first time). Then buffers will
only be added when more than one thread passes
through the function simultaneously. See the example
in main.

You only need as many buffers as the amount of passing
through the function in question simultaneoulsy.


This depends on your OS. Most OS's have mechanisms
that only cause significant reduction in
performance when contention arises (switching to
Kernel mode). In windows you could typically wrap
the critical section (I think boost or a library
like LOKI will have done this for your already
with some scoped locking mechanism). Under Windows
you should rather use CRITICAL_SECTION (and not
MUTEX) as MUTEX is for interprocess synchronization
which has more overhead.

Regards,

Werner

Alright, I'll do that then.

Thanks for the answers.

 

[terminator]

I wrote a little test using VecStack I mentioned below. One
has to consider that the test ran in a single threaded
environment and things may change if you throw a
critical section in there (but not to much if not
contented). I used Dev C++ (don't know which STL),
turned debugging off and enabled optimization for
speed. Turned out the vector code executed faster
than the array code by +10 seconds for 30000000
items. Test is below:

#include <iostream>
#include <cassert>
#include <vector>
#include <memory>
//...#include "yourMutex.h"

template <class T>
struct VecStack
{
typedef std::auto_ptr<std::vector<T> > ClientItem;

VecStack( unsigned defaultSz )
: defaultSz_( defaultSz )
{ vecList_.reserve( 50 ); }

ClientItem pop()
{
//...Mutex::guard lock( mutex_ );
std::auto_ptr<std::vector<T> > v( 0 );

if( vecList_.empty() )
{
v.reset( new std::vector<T>( defaultSz_ ) );
}
else
{
v.reset( vecList_.back() );
vecList_.pop_back();
}
return v;
}

pop can be designed better so that it never returns a null in a
multithreaded environment:

ClientItem pop(){
//...Mutex::guard lock( mutex_ );
//do{
if( ! vecList_.empty() )
{
ClientItem v ( vecList_.back() );
vecList_.pop_back();
if(v.get()!=0)
return v;
};
//}while(v.get()==0);
//reach here if ( vecList_.empty() ||
(vecList_.pop_back().get()==NULL) )

void push( ClientItem v )
{
//...Mutex::guard lock( mutex_ );
//assert( v.get() );
vecList_.push_back( v.release() );
}

private:
std::vector<std::vector<T>*> vecList_;
unsigned defaultSz_;
//...Mutex mutex_;

};

enum
{
eMAX_EXPECTED_SZ = 512,
eLOOP_SZ = 30000000,
eINNER_SZ = 500

};

void testVect1( unsigned len )
{
typedef VecStack<int> StackType;
static StackType stack( eMAX_EXPECTED_SZ );

StackType::ClientItem item = stack.pop();
item->resize( len );
stack.push( item );}

void testVect2( unsigned len )
{
int Items[eMAX_EXPECTED_SZ] = { 0 };}

void doTest( void(*op)(unsigned) )
{
for( int i = 0; i < eLOOP_SZ/eINNER_SZ; ++i )
{
for( int j = 0; j < eINNER_SZ; ++j )
{
(*op)( j );
}
}

}

int main(int argc, char *argv[])
{
std::cout << "Press key to start test!" << std::endl;
std::cin.get();
std::cout << "Test1 running...\n";
doTest( testVect1 );
std::cout << "Test2 running... \n";
doTest( testVect2 );
std::cout << "End... Press key to exit." << std::endl;
std::cin.get();
return EXIT_SUCCESS;

}

you can also define an allocator instead of a vecstack with similar
implementation(cache a few pointers and allocate new memory if cache
is full).

regards,
FM.

 

[werasm]

pop can be designed better so that it never returns a null in a
multithreaded environment:

I don't follow - currently it never returns a null. The
idea is that you can pop from an empty stack. I probably
should not call it stack as it is more of an allocator.

you can also define an allocator instead of a vecstack with similar
implementation(cache a few pointers and allocate new memory if cache
is full).

Yes, you could use an allocator interface. I don't think
caching pointers will buy you that much though. Perhaps
give an example.

Regards,

Werner

 

[werasm]

pop can be designed better so that it never returns a null in a
multithreaded environment:

My idea was rather to prevent pushing NULL onto
the stack. Therefore implementation of push
becomes:

assert( v.get() );
Mutex::guard lock( mutex_ );
vecList_.push_back( v.release() );

or even...

if( v.get() != NULL )
{
Mutex::guard lock( mutex_ );
vecList_.push_back( v.release() );
}

.... as popping from the empty stack is OK
in this case. The only thing that I don't like
about the above is it is not consistent with
traditional stack. Therefore an allocator
interface/adapter would be better, yes. Still
don't follow the whole caching of pointers, or
I don't think it will buy you much.

Regards,

Werner

 

[terminator]

My idea was rather to prevent pushing NULL onto
the stack. Therefore implementation of push
becomes:

assert( v.get() );
Mutex::guard lock( mutex_ );
vecList_.push_back( v.release() );

or even...

if( v.get() != NULL )
{
Mutex::guard lock( mutex_ );
vecList_.push_back( v.release() );

}

... as popping from the empty stack is OK
in this case. The only thing that I don't like
about the above is it is not consistent with
traditional stack. Therefore an allocator
interface/adapter would be better, yes. Still
don't follow the whole caching of pointers, or
I don't think it will buy you much.

Regards,

Werner

mistake is mine don`t worry

really sorry

 

[werasm]

mistake is mine don`t worry

No, perhaps you are right though. Calling
the data structure a stack is slightly
confusing. It's more of a vector pool
implemented in terms of an underlying
stack.

Perhaps...

template <class T>
struct VecStack
{
//...
ClientItem get();
void put( ClientItem v );
//...
};

.... would be a clearer interface.

Regards,

Werner

 

[terminator]

No, perhaps you are right though. Calling
the data structure a stack is slightly
confusing. It's more of a vector pool
implemented in terms of an underlying
stack.

Perhaps...

template <class T>
struct VecStack
{
//...
ClientItem get();
void put( ClientItem v );
//...

};

... would be a clearer interface.

Regards,

Werner

I still think that it is better to use this pattern(with minor
modifications) for an allocator , not a stack of vectors.

regards,
FM.

 

[werasm]

I still think that it is better to use this pattern(with minor
modifications) for an allocator , not a stack of vectors.

Without a little example I'm in the dark as to what you
mean. Which pattern - the one I've suggested, and what
minor modifications? I would love the example as I believe
I might learn something in the process. I've contemplated
traditional allocators but to me this is just not the
same thing. Care to take the time to give an example?

Regards,

Werner