Fast bit mask check

Help!
1

Hi,

I’d like write a really fast predicate that checks a bit pattern stored in an integer via a bit mask.

If all bits in the mask are also set in the integer, then the predicate should succeed, otherwise fail.

Here is a stab at it.

I am assuming that only if Bits has exactly the same bits set as indicate in Mask, then Result and Mask will be equal, otherwise not.

check_equal_to_mask(Bits, Mask) :-
Result is Bits /\ Mask,
Result == Mask.

In, say, C, the a function returning the conditional (Bits /\ Mask) would already be true or false, no need for an extra check, leading to a faster response – i think.

any thoughts are much appreciated,

Dan

2

If you have to do lots of these, then I would write it in C and use the Foreign Language Interface. I have never used this but the SWI-Prolog GitHub repository has lots of working code for examples.

If you only have a few stable mask, then I would skip the Foreign Language Interface and use indexing, e.g.

check_equal_to_mask(0x01).
check_equal_to_mask(0x02).
check_equal_to_mask(0x0A).
check_equal_to_mask(0x14).
  ...

If you have many stable patterns but they can reduce using a Karnaugh map, then do the reduction and again use indexing.

check(V) :-
   check_equal_to_mask_01(V)
check(V) :-
   check_equal_to_mask_02(V)).
  ...

check_equal_to_mask_01(0x02) .
check_equal_to_mask_01(0xAE).

check_equal_to_mask_02(0xC2).
check_equal_to_mask_02(0x06).
check_equal_to_mask_02(0xFE).

If you want it really fast and there are several logic processing steps in a row that can be done in assembly, then drop into C and have that drop in to assembly. For each different processor the code would have to be re-written.

3

Thank you.

I am not sure how the lookup could work in my case – but, it would in fact mean a hash look up instead the mask computation and equal check.

I have been avoiding going to C, but it seems that this would be the fastest.

I am, however, also wondering what the overhead is to call a foreign predicate and get a responds back into prolog. Even if the processing in C is very fast there could in addition be some overhead for parameter passing back and forth, and cleanup – i guess.

Dan

4

I take it that you understand that unification is the heart of Prolog and that it is done sometimes in the billions of operations for one query. Notice here that unification is done in C to make it faster.

Look at some the queries here and the inference count in the billions (3,126,154,467) and the time to execute (671.015 seconds).

5

Thank you.

It really depends on the system requirements and the processor this should work on.

I have, for example, looked at running on a regular mobile (android) device, or smaller, and am currently looking at how far i can optimize my code before dropping down to foreign predicates in C – or even rewriting critical portion in C – due to such interface overheads.

It seems that even small changes in approach can have quite a bit of impact.

Dan

6

Is the same as this:

check_equal_to_mask(Bits, Mask) :-
    Mask =:= Bits /\ Mask.

If this is vital to performance, make sure to compile using -O to inline arithmetic rather than calling the predicate. This alternative should be faster because it avoids converting Result back to Prolog and it converts Mask only once to native.

In theory the compiler could have done that if it was written as Result =:= Mask, but SWI-Prolog’s compiler is rather naive.

1 Like