3
\$\begingroup\$

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;

    to_handle = test_const1;

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

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  > ConstraintsContainer_t;
    ConstraintsContainer_t constraints_;
    ConstraintsContainer_t choosen_;

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=356a9d8c94bddf6721f98bbc44c74fec-71380fc8ea55c1ab9f744d79fff5379c

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

Any help is appreciated!

\$\endgroup\$
  • \$\begingroup\$ So to be chosen (the first time), the item has to be zero (item & to_handle == item with to_handle=0). Or is that meant to be test_const1? \$\endgroup\$ – Useless May 1 '13 at 15:06
  • \$\begingroup\$ Hello, thanks for helping! you're right to_handle is to be set to test_const1 indeed \$\endgroup\$ – Syffys May 1 '13 at 15:09
  • \$\begingroup\$ So, you set to_handle = test_const1 somewhere? Or the first test is meant to be item & test_const1 == item? \$\endgroup\$ – Useless May 1 '13 at 15:11
1
\$\begingroup\$

to_handle actually varies, but the test_consts are all constant, so we can give the compiler a hint here

const uint32_t test_const1 = Constraint3::VAL1 + Constraint3::VAL2;
const uint32_t test_const2 = Constraint1::VAL2 + Constraint1::VAL4 + Constraint1::VAL8;
const uint32_t test_const3 = Constraint2::VAL1 +  Constraint2::VAL2 + Constraint2::VAL4;

uint32_t to_handle = test_const1;
for(ConstraintsContainer_t::iterator it = constraints_.begin(); it != constraints_.end(); ++it) {

EDIT

I've just seen from the linked code that the posted code is completely wrong. So, the remainder of this answer is unlikely to be helpful.

I will however observe that you're timing both the operations you sort-of show above, but also the formatted output. Are you sure you're timing the right thing?


now, we de-reference your iterator a lot in this loop. I don't know how easily the compiler can handle it here, but IMO this is more readable:

    auto &item = it->get();

(if you don't have C++11 auto, just put the actual type in - I don't know what it is here)

    if( (item & to_handle) == item &&
        (item & test_const2) == item &&
        (item & test_const3) == item ) {
        choosen_.push_back((*it));
        to_handle -= item;
    }
}

Now, the second two conditions in your if never vary, and they simply test that all the set bits of item are inside both masks test_const2=0x0E and test_const3=0x07. That is, none of the set bits are outside test_const2 & test_const3, so

const uint32_t fail_test = ~(test_const2 & test_const3);

//...

    if( (item & to_handle) == item &&
        (item & fail_test) == 0) {
        choosen_.push_back((*it));
        to_handle -= item;
    }

again, the optimizer might have figured that out already, but this version is anyway more expressive.

\$\endgroup\$
  • \$\begingroup\$ thanks again for helping! Sorry, I did not mention that this is supposed to process variable sets of (test_const1,test_const2,test_const3). But you're right, timing the display section is not really appropriate... \$\endgroup\$ – Syffys May 1 '13 at 15:54
  • \$\begingroup\$ None of your posted (or linked) code process variable sets, only constant ones. Performance depends on the actual code, so showing two different versions, neither of which do the same thing you're trying to optimise, won't help you. FWIW though, setting the destination vector size in advance might help. It can't be bigger than the input, so choosen_.reserve(constraints_.size()) before the loop (and timing start!) could help. \$\endgroup\$ – Useless May 1 '13 at 17:11
  • \$\begingroup\$ I get your point, maybe my post was not clear enough then: my question is as much about the specific ways of implementation (in my case: iterating over a complete vector) as the compiler optimization technics. So probably, this is not enough to state about the compiler optimization technics, but it should be enough to state about the various options of implementation (for example, indexed containers and if some feedback could confirm that this is viable, which kind and how)... \$\endgroup\$ – Syffys May 1 '13 at 19:20
  • \$\begingroup\$ You're asking for help with designing an algorithm by asking us to review code that does something slightly different? You need to figure out the algorithm first, I'm afraid. Hammering your broken code until the algorithm makes sense is unlikely to work. \$\endgroup\$ – Useless May 2 '13 at 17:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.