Selecting element from a collection based on bitwise-and result

[Syffs]

I need to improve this section of code:
***********
uint32_t to_handle = 0;
uint32_t test_const1 = Constraint3::VAL1 + Constraint3::VAL2;
uint32_t test_const2 = Constraint1::VAL2 + Constraint1::VAL4 +
Constraint1::VAL8;
uint32_t test_const3 = Constraint2::VAL1 + Constraint2::VAL2 +
Constraint2::VAL4;

for(ConstraintsContainer_t::iterator it = constraints_.begin(); it !=
constraints_.end(); ++it) {
if( ( ((*it).get<0>() & to_handle) == (*it).get<0>() ) &&
( ((*it).get<1>() & test_const2) == (*it).get<1>() ) &&
( ((*it).get<2>() & test_const3) == (*it).get<2>() ) ) {
choosen_.push_back((*it));
to_handle -= (*it).get<0>();
}
}
***********

Here are declarations:
***********
namespace Constraint1 {
typedef enum {
NONE = 0x00000000,
VAL1 = 0x00000001,
VAL2 = 0x00000002,
VAL4 = 0x00000004,
VAL8 = 0x00000008,
ALL = 0xFFFFFFFF
} Type;
}
namespace Constraint2 {
typedef enum {
NONE = 0x00000000,
VAL1 = 0x00000001,
VAL2 = 0x00000002,
VAL4 = 0x00000004,
VAL8 = 0x00000008,
ALL = 0xFFFFFFFF
} Type;
}
namespace Constraint3 {
typedef enum {
NONE = 0x00000000,
VAL1 = 0x00000001,
VAL2 = 0x00000002,
VAL4 = 0x00000004,
VAL8 = 0x00000008,
VAL16 = 0x00000010,
VAL32 = 0x00000020,
ALL = 0xFFFFFFFF
} Type;
}
typedef std::vector<boost::tuple<uint32_t, uint32_t, uint32_t> >
ConstraintsContainer_t;
ConstraintsContainer_t constraints_;
***********

The goal is to select elements from a collection by performing a
bitwise and on them.

Order of insertion in that vector matters and number of element
should reach about 100. It's currently taking about 50 microseconds
to complete this section of codes, I'd need to make it 10-20
microseconds if possible.

Here is the source code on a live workspace if it helps:
http://coliru.stacked-crooked.com/view?id=356a9d8c94bddf6721f98bbc44c7
4fec-71380fc8ea55c1ab9f744d79fff5379c

I've tryed to use boost multi_index_containers, but it'd require to
get this to work:
http://stackoverflow.com/questions/16101886/boost-multi-index-containe
r-with-composite-key-and-logical-and-comparison

Any help is appreciated, thanks in advance!


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

[Chris Uzdavinis]

On Wednesday, May 1, 2013 12:30:02 PM UTC-5, Syffs wrote:

> for(ConstraintsContainer_t::iterator it = constraints_.begin(); it !=
>
> constraints_.end(); ++it) {
>
> if( ( ((*it).get<0>() & to_handle) == (*it).get<0>() ) &&
> ( ((*it).get<1>() & test_const2) == (*it).get<1>() ) &&
> ( ((*it).get<2>() & test_const3) == (*it).get<2>() ) ) {
> choosen_.push_back((*it));
> to_handle -= (*it).get<0>();
> }
> }

> Order of insertion in that vector matters and number of element
> should reach about 100. It's currently taking about 50 microseconds
> to complete this section of codes, I'd need to make it 10-20
> microseconds if possible.

I notice that your timing window includes both your calculation
loop AND your output-writing loop.

Don't measure the output time, because IO is slow and
dominates the time so significantly that the rest is meaningless.
If you include the IO time, then there is nothing you can do
to significantly change the result. Even if your calculation loop
took literally 0 cycles to complete, it still would have little
impact on the overall time, since it's just a drop in the bucket
in comparison.

Simply moving the call to clock_gettime to be immediately after your
computation loop shows timing improvement by a factor of 100. That
is, 175226 nanoseconds (originally) becomes to 1983 after not counting
the output. Presumably the computation is the important part?

If you need high(er) speed output, then that's a different question
entirely.

Chris

[Syffs]

{ Your article lacks the context of what it's referring to.
Please include some quoting to establish the context. -mod }

Thanks for helping!

Indeed, I noticed that I was timing the output part, and you're right
that makes the processing part fall to about 2 microseconds. Now that's
for about 50 entries in my vector, which means that more entries is
going to affect significantly this value.

Hence I'm wondering if someone had something different in mind (like
some indexed container) which would allow to implement a similar
mechanism and scale the performances with an increased number of entries...

[Francis Glassborow]

On 03/05/2013 18:45, Syffs wrote:
> { Your article lacks the context of what it's referring to.
> Please include some quoting to establish the context. -mod }
>
> Thanks for helping!
>
> Indeed, I noticed that I was timing the output part, and you're right
> that makes the processing part fall to about 2 microseconds. Now that's
> for about 50 entries in my vector, which means that more entries is
> going to affect significantly this value.

I do not understand that. Even with relocation due to growth a vector
should scale well (the only problem is the potential for fragmenting the
address space,

>
> Hence I'm wondering if someone had something different in mind (like
> some indexed container) which would allow to implement a similar
> mechanism and scale the performances with an increased number of entries...
>

Unless you know the size a vector should work fine. However it is still
worth while starting it with something near the capacity that you will
eventually require as that will minimise relocation.

Francis