Ropes

Useful Code
1

Hi all,
I’ve implemented the Rope/Cord data structure in SWI-Prolog to do some experimentations for a workload that needs to synchronize text against many small changes.
Ropes are supposed to be good for such scenarios because they have split and concatenation operations that take O(log n) where n is the equivalent string’s length, where an array-based string would take O(n) time.

I couldn’t find an existing Prolog implementation online and I thought this might be useful for someone else somewhen, so I’ve added some doc comments and uploaded the code here.

Here’s an example usage:

test(edit) :-
    string_rope("Hello, World!"  , HW),
    string_rope("Here be dragons", HD),
    rope_split(HD, 8, _, D),  % "Here be " + "dragons"
    rope_split(HW, 7, H, W),  % "Hello, "  + "World!"
    rope_split(W , 5, _, E),  % "World"    + "!"
    rope_concat(H , D, HS),
    rope_concat(HS, E, HE),
    rope_string(HE, HF),
    assertion(HF == "Hello, dragons!").

EDIT:
Here’s a little benchmark showing the scalability of repeatedly editing ropes compared to strings (running on MacBook Pro with Intel i9):

?- bench(ropes, 1024, 1048576, D).  % 1 MB string, 1024 edits
D = 0.27640414237976074.

?- bench(ropes, 1024, 10485760, D). % 10MB string, 1024 edits
D = 0.4560530185699463.

?- bench(strings, 1024, 1048576, D).
D = 5.052635908126831.

?- bench(strings, 1024, 10485760, D).
D = 58.68148612976074.

Where the benchmark routine simply splits the string in a random offset and concatenates the two parts back together:

bench(Impl, Rounds, Size, Time) :-
    setup_call_cleanup(open("/dev/urandom", read, Random),
                       read_string(Random, Size, S0),
                       close(Random)),
    prepare_string(Impl, S0, S),
    get_time(T0), bench_(Impl, Rounds, S, Size), get_time(T),
    Time is T - T0.

bench_(_, 0, _, _) :- !.
bench_(I, N, S, L) :-
    random(0, L, J),
    split_concat_rountrip(I, S, J, R),
    M is N - 1,
    bench_(I, M, R, L).

split_concat_rountrip(strings, S, I, R) :-
    sub_string(S, 0, I, _, A),
    sub_string(S, I, _, 0, B),
    string_concat(A, B, R).
split_concat_rountrip(ropes, S, I, R) :-
    rope_split(S, I, A, B),
    rope_concat(A, B, R).

prepare_string(strings, S, S).
prepare_string(ropes, S, R) :- string_rope(S, R).

Cheers

6 Likes