[ovs-dev] [PATCH 6/7] lib/flow: Reduce calls to count_1bits().

[Jarno Rajahalme]

Ben,

This is much cleaner, thanks!

Acked-by: Jarno Rajahalme <jrajahalme at nicira.com>


On Oct 6, 2014, at 2:17 PM, Ben Pfaff <blp at nicira.com> wrote:

> On Wed, Oct 01, 2014 at 04:02:36PM -0700, Jarno Rajahalme wrote:
>> Depending on the CPU, count_1bits() may be more or less expensive, so
>> it is better to avoid unnecessary calls to it.  When the map has
>> consecutive 1-bits, those can be cleared without counting.
>> 
>> Signed-off-by: Jarno Rajahalme <jrajahalme at nicira.com>
>> ---
>> lib/flow.h |    3 ++-
>> 1 file changed, 2 insertions(+), 1 deletion(-)
>> 
>> diff --git a/lib/flow.h b/lib/flow.h
>> index 9bb9a58..a6e75c7 100644
>> --- a/lib/flow.h
>> +++ b/lib/flow.h
>> @@ -507,7 +507,8 @@ mf_get_next_in_map(uint64_t *fmap, uint64_t rm1bit, const uint32_t **fp,
>>             *fmap -= trash;
>>             *fp += count_1bits(trash);
>>         }
>> -        *value = **fp;
>> +        *fmap -= rm1bit;
>> +        *value = *(*fp)++;
>>     }
>>     return rm1bit != 0;
>> }
> 
> I think that MINIFLOW_FOR_EACH_IN_MAP can be improved in other ways.
> rm1bit_ seems unnecessary: it is always rightmost_1bit(map_) at point
> of use, so it could be calculated inside mf_get_next_in_map() if &map
> were passed in instead.  Also, it seems a bit awkward to have
> declarations outside the for loop.
> 
> What do you think of this version?  It incorporates your improvement
> but avoids the out-of-for-statement declarations and moves the rm1bit
> calculation inside the function.  It passes the unit tests for me.
> 
> struct mf_for_each_in_map_aux {
>    const uint32_t *values;
>    uint64_t fmap;
>    uint64_t map;
> };
> 
> static inline bool
> mf_get_next_in_map(struct mf_for_each_in_map_aux *aux, uint32_t *value)
> {
>    if (aux->map) {
>        uint64_t rm1bit = rightmost_1bit(aux->map);
>        aux->map -= rm1bit;
> 
>        if (aux->fmap & rm1bit) {
>            /* Advance 'aux->values' to point to the value for 'rm1bit'. */
>            uint64_t trash = aux->fmap & (rm1bit - 1);
>            if (trash) {
>                aux->fmap -= trash;
>                aux->values += count_1bits(trash);
>            }
> 
>            /* Retrieve the value for 'rm1bit' then advance past it. */
>            aux->fmap -= rm1bit;
>            *value = *aux->values++;
>        } else {
>            *value = 0;
>        }
>        return true;
>    } else {
>        return false;
>    }
> }
> 
> /* Iterate through all miniflow u32 values specified by 'MAP'. */
> #define MINIFLOW_FOR_EACH_IN_MAP(VALUE, FLOW, MAP)                      \
>    for (struct mf_for_each_in_map_aux aux__                            \
>             = { miniflow_get_u32_values(FLOW), (FLOW)->map, MAP };     \
>         mf_get_next_in_map(&aux__, &(VALUE));                          \
>        )