I tried to compare string concatenation using ropes and system's add, but seems the bench mark result is not right... Does anyone know how to use this module efficiently? (Also, I must admit that I never used rope algorithm, so I might doing wrong)
import times, ropes proc strBench(sample: Rope|string) = var str = when sample is Rope: rope("") else: "" let startTime = getTime() defer: let endTime = getTime() echo endTime.toSeconds() - startTime.toSeconds() for i in 0 .. 6_000_000: str.add sample const sample = "something\n" strBench(sample.rope()) strBench(sample) # nim c -r rope_test.nim # rope version -> 3 sec # normal version -> 1 sec
Is my understanding correct that both string and Rope have O(1) appends?
I think string has amortized O(1) due to growing buffer space, whereas Rope has straight-up O(1) runtime complexity.
But what might matter more here is the constant factor, and I think string ends up doing much fewer allocations than Rope, which has to allocate many objects on the heap for every iteration.
Rope would get an edge if you needed to do many random inserts/deletes in the middle of a very long string.