std::set, index of element

[Hicham Mouline]

Hello

we have a perf critical function that calculates for 1 thing, many
operations, and returns for each 1 result and 1 code.

codes and results are outputs, operationSet is the input.

Calculate( CalcCode codes[], double results[], const CalcOperationSet&
operationSet, int thing)
{
if ( operationSet.IsSet( ... ) ) {
// do operation and store in results
}
...
}

Before that, I had
Calculate ( std::map<CalcOperation, pair<CalcCode, double> >& output, const
CalcOperationSet& operationSet, int thing)
but it is a 4 times slower than the above version in a typical usage.

So we will go with the native array based solution.

Note, the size of the array is equal to the size of the set. The array is
preallocated outside of the loop calling Calculate.

enum CalcOperation { // 3rd party lib
OP1 = 4023,
OPtwo = 2349,
OPthree = 4,
....
// 500 elements
};



I wish to index the operations set in operationSet, so that I can extract a
size_t index to use for codes and results.

The calling contexts have a static number of operations you pass in the set,
but there are many different calling contexts.

1 context would look like:


CalcOperationSet operationSet; operationSet.set( OP1 );
operationSet.set( OPthree ); operationSet.set( OPtwo );
double results[3]; CalcCode codes[3];
// somehow associate OP1 with 0, OPthree with 1 and OPtwo with 2
// of course, OP1 with 0 depends on the context , here we have a set with
just 3 elements
// can we determine the order of insertion
for (size_t s=0; s<1000; ++s)
Calculate(results, codes, operationSet, things );



regards,

 

[Michael DOUBEZ]

Hello

we have a perf critical function that calculates for 1 thing, many
operations, and returns for each 1 result and 1 code.

codes and results are outputs, operationSet is the input. [...]

I wish to index the operations set in operationSet, so that I can extract a
size_t index to use for codes and results.

The calling contexts have a static number of operations you pass in the set,
but there are many different calling contexts.

1 context would look like:

CalcOperationSet operationSet; operationSet.set( OP1 );
operationSet.set( OPthree ); operationSet.set( OPtwo );
double results[3]; CalcCode codes[3];
// somehow associate OP1 with 0, OPthree with 1 and OPtwo with 2
// of course, OP1 with 0 depends on the context , here we have a set with
just 3 elements
// can we determine the order of insertion
for (size_t s=0; s<1000; ++s)
Calculate(results, codes, operationSet, things );

How would we know?
That depends on the type of CalcOperationSet.

If you have an iterator in CalcOperationSet you can easily associate
operation to result and for the other way around, from an index, you can
use std::advance to advance your iterator but performances depends on
the type of iterator (which must be at least a FowardIterator).

 

[Hicham Mouline]

Hello

we have a perf critical function that calculates for 1 thing, many
operations, and returns for each 1 result and 1 code.

codes and results are outputs, operationSet is the input. [...]

I wish to index the operations set in operationSet, so that I can extract
a size_t index to use for codes and results.

The calling contexts have a static number of operations you pass in the
set, but there are many different calling contexts.

1 context would look like:

CalcOperationSet operationSet; operationSet.set( OP1 );
operationSet.set( OPthree ); operationSet.set( OPtwo );
double results[3]; CalcCode codes[3];
// somehow associate OP1 with 0, OPthree with 1 and OPtwo with 2
// of course, OP1 with 0 depends on the context , here we have a set with
just 3 elements
// can we determine the order of insertion
for (size_t s=0; s<1000; ++s)
Calculate(results, codes, operationSet, things );

How would we know?
That depends on the type of CalcOperationSet.

If you have an iterator in CalcOperationSet you can easily associate
operation to result and for the other way around, from an index, you can
use std::advance to advance your iterator but performances depends on the
type of iterator (which must be at least a FowardIterator).

CalcOperationSet is a std::set, and so finding the index of the operation
inside the set,
using std::distance is not ideal.

I just switched to std::map< CalcOperation, size_t >, wrapper by
CalcOperations
and I actually store the index of each operation.
It is twice as fast than std::set in this usage case.

So


CalcOperations operations;
operations.set( OP1 ); operations.set( OPthree ); operations.set(
OPtwo );
double results[3]; CalcCode codes[3];

for (size_t s=0; s<1000; ++s) {
Calculate( codes, results, operations, things ) ;
// use results and codes
}





Calculate( Code codes[], double results[], const CalcOperations& operations
, int thing )
{
if ( operations.IsSet( OP1 )
{
results [ operations.IndexOf(OP1 ) ] = ....
}
if ( operations.IsSet( OPthree )
{

}
// I have now factorized redundance runtime between OPxxx and OPyyy
// I can in 1 call to Calcuate get both results rather than call the
single version of Calculate
// a first time, then a second time and so on, which needlessly runs some
costly code more than once.
}



Your comments are appreciated,

regards,

 

[Hicham Mouline]

Let's be clear about what this means: you changed the kind of container
and changed how you track locations, and the result is faster. map and set
typically use the same code under the covers. The difference you see comes
from changing how you track locations.

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

With a set, i used to find the index of the operation with std::distance()
which is slow.

With the map<Operation, size_t>, I actually stored the index as the value,
so all that
was involved is the [] operator to read the index directly.
It makes sense it is faster.

H