# Effective implementation of a set

**URL:** <https://swi-prolog.discourse.group/t/effective-implementation-of-a-set/1713>\
**Category:** Help!\
**Created:** [January 7, 2020, 2:37pm UTC](https://swi-prolog.discourse.group/t/effective-implementation-of-a-set/1713 "2020-01-07T14:37:06Z")\
**Posts on this page:** 1\
**Showing post:** 8

<div class="post-metadata">

**Author:** ![Boris](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/boris/32/7486_2.png) [@Boris](https://swi-prolog.discourse.group/u/Boris)\
**Post date:** [February 26, 2020, 9:41am UTC](https://swi-prolog.discourse.group/t/effective-implementation-of-a-set/1713/8 "2020-02-26T09:41:02Z")

</div>

> [@jan](#):
>
> Using an integer bitmap and the X _1000_ Y encoding might b e worth trying 🙂

I tried this out, here is a short write-up.

TL;DR: When very large integers are involved, `set_prolog_flag(optimise, true)` does not seem to help (on my machine). Also, choosing the right algorithm does make a difference.

* * *

The original problem statement can be found here:

> **[Day 6 - Advent of Code 2015](https://adventofcode.com/2015/day/6)**

The essence of the problem is to apply a couple of hundred (300 exactly) instructions (set/reset/flip) to a 1\_000\_000 element bitset. Every instruction is defined as a rectangle in a 1000x1000 bitmap. The question at the end is “how many bits in the bitmap are on”.

At the bottom of this post you can find the full code listings and the running times I measured. The interesting bits:

- Yes, it is perfectly fine to make an integer with 1\_000\_000 bits and set/reset/flip those.
- In my original solution, most of the time (95% of about a second) went into generating the “rectangular bitmasks”. The time is spend inside is/2!
- Using `set_prolog_flag(optimise, true)` **increases the runtime slightly**.

The original code for preparing the rectangular bitmasks looked like this:

```prolog
bitmask(X0, Y0, X1, Y1, Mask) :-
    Row is (1 << (X1 - X0 + 1)) - 1,
    N_cols0 is Y1 - Y0,
    rectangle(N_cols0, Row, 1000, Mask0),
    Mask is Mask0 << (X0 + 1000 * Y0).

rectangle(N_cols, Row, Shift, Mask) :-
    ( succ(N_cols0, N_cols)
    -> rectangle(N_cols0, Row, Shift, Mask0),
        Mask is (Mask0 << Shift) + Row
    ; Mask = Row
    ).

```

This is where the program was spending 95% of its time. The only idea I could come up to improve this was to instead use the “power of associative operation” algorithm for creating the bitmask; the idea is outlined on pages 31-40 [of this PDF](http://elementsofprogramming.com/eop.pdf); obviously, this idea is ancient (like, ancient Egypt) but I think that this is where I originally stole the code from.

Long story short, as expected, this decreases the running time by a factor of 10 (from 11 seconds down to 0.8 seconds for 10 runs), and is/2 no longer dominates when I profile. The power we are raising to is anything between 1 and 1000 (for my input, mean is 266 and median is 207).

If there is interest, I can wrap up inside a module the “raising to power with associative operation” code I have and post it here.

* * *

## Code listings

### Original solution

```prolog
:- module(d06, [run/2]).

run(Filename, N) :-
    phrase_from_file(light_instr(0, Lights), Filename),
    N is popcount(Lights).

light_instr(L0, L) -->
    instr(A, X0, Y0, X1, Y1), !,
    { do_instr(A, X0, Y0, X1, Y1, L0, L1) },
    light_instr(L1, L).
light_instr(L, L) --> [].

do_instr(A, X0, Y0, X1, Y1, L0, L1) :-
    bitmask(X0, Y0, X1, Y1, Mask),
    apply_mask(A, Mask, L0, L1).

bitmask(X0, Y0, X1, Y1, Mask) :-
    Row is (1 << (X1 - X0 + 1)) - 1,
    N_cols0 is Y1 - Y0,
    rectangle(N_cols0, Row, 1000, Mask0),
    Mask is Mask0 << (X0 + 1000 * Y0).

rectangle(N_cols, Row, Shift, Mask) :-
    ( succ(N_cols0, N_cols)
    -> rectangle(N_cols0, Row, Shift, Mask0),
        Mask is (Mask0 << Shift) + Row
    ; Mask = Row
    ).

apply_mask(set, Mask, L0, L1) :-
    L1 is L0 \/ Mask.
apply_mask(reset, Mask, L0, L1) :-
    L1 is L0 /\ ((1 << 1_000_000) - Mask - 1).
apply_mask(flip, Mask, L0, L1) :-
    L1 is xor(L0, Mask).

:- use_module(library(dcg/basics)).

instr(A, X0, Y0, X1, Y1) -->
    action(A), " ",
    integer(X0), ",", integer(Y0),
    " through ",
    integer(X1), ",", integer(Y1),
    "\n".

action(set) --> "turn on".
action(reset) --> "turn off".
action(flip) --> "toggle".

```

Running this on my computer, with my input (you can download it from the “Advent of Code” website I linked above):

```prolog
?- time( forall(between(1, 10, _), run('d06.input', N)) ).
% 2,605,420 inferences, 11.797 CPU in 11.879 seconds (99% CPU, 220851 Lips)
true.

```

### “Power-semigroup” solution

```prolog
:- module(d06, [run/2]).

:- use_module(library(dcg/basics), [integer//1]).

run(Filename, N) :-
    phrase_from_file(light_instr(0, Lights), Filename),
    N is popcount(Lights).

light_instr(L0, L) -->
    instr(A, X0, Y0, X1, Y1), !,
    { format(user_error, "~d,", [Y1 - Y0 + 1]) },
    { do_instr(A, X0, Y0, X1, Y1, L0, L1) },
    light_instr(L1, L).
light_instr(L, L) --> [].

do_instr(A, X0, Y0, X1, Y1, L0, L1) :-
    Row_mask is ((1 << (X1 - X0 + 1)) - 1) << X0,
    N is Y1 - Y0 + 1,
    power_semigroup(m(Row_mask, 1000), N, append_rows, m(Mask0, _)),
    Mask is Mask0 << (1000 * Y0),
    apply_mask(A, Mask, L0, L1).

append_rows(m(M_a, N_a), m(M_b, N_b), m(M, N)) :-
    M is (M_a << N_b) + M_b,
    N is N_a + N_b.

apply_mask(set, Mask, L0, L1) :-
    L1 is L0 \/ Mask.
apply_mask(reset, Mask, L0, L1) :-
    L1 is L0 /\ ((1 << 1_000_000) - Mask - 1).
apply_mask(flip, Mask, L0, L1) :-
    L1 is xor(L0, Mask).

instr(A, X0, Y0, X1, Y1) -->
    action(A), " ",
    integer(X0), ",", integer(Y0),
    " through ",
    integer(X1), ",", integer(Y1),
    "\n".

action(set) --> "turn on".
action(reset) --> "turn off".
action(flip) --> "toggle".

/* raise to power */
goal_expansion(odd(N), N /\ 0x1 =:= 1).
goal_expansion(half(N, Half), Half is N >> 1).

power_accumulate_semigroup(R, A, N, Op, P) :-
    ( N == 0
    -> P = R
    ; power_accumulate_semigroup_1(R, A, N, Op, P)
    ).

power_accumulate_semigroup_1(R, A, N, Op, P) :-
    ( odd(N)
    -> power_accumulate_semigroup_oddn(R, A, N, Op, P)
    ; power_accumulate_semigroup_anyn(R, A, N, Op, P)
    ).

power_accumulate_semigroup_oddn(R, A, N, Op, P) :-
    call(Op, R, A, R1),
    ( N == 1
    -> P = R1
    ; power_accumulate_semigroup_anyn(R1, A, N, Op, P)
    ).

power_accumulate_semigroup_anyn(R, A, N, Op, P) :-
    half(N, N1),
    call(Op, A, A, A1),
    power_accumulate_semigroup_1(R, A1, N1, Op, P).

power_semigroup(A, N, Op, P) :-
    must_be(positive_integer, N),
    power_semigroup_(A, N, Op, P).

power_semigroup_(A, N, Op, P) :-
    power_semigroup_evenn(A, N, Op, A0, N0),
    ( N0 == 1
    -> P = A0
    ; call(Op, A0, A0, A1),
        half(N0 - 1, N1),
        power_accumulate_semigroup(A0, A1, N1, Op, P)
    ).

power_semigroup_evenn(A, N, Op, A1, N1) :-
    ( odd(N)
    -> A = A1,
        N = N1
    ; call(Op, A, A, A0),
        half(N, N0),
        power_semigroup_evenn(A0, N0, Op, A1, N1)
    ).

```

Time:

```prolog
?- time( forall(between(1, 10, _), run('d06.input', N)) ).
% 414,149 inferences, 0.740 CPU in 0.756 seconds (98% CPU, 559307 Lips)
true.

```

---

_[View the full topic](https://swi-prolog.discourse.group/t/effective-implementation-of-a-set/1713)._