Efficiently building strings

[JanBeh]

Hi, this is a newbie question. I wonder how to efficiently build strings in Koka. In particular:

What is the cost of successivly concatenating a small string to another string that grows. I.e. would the following have quadratic runtime?

fun main()
  var acc : string := ""
  for (1,100) fn(_) acc := acc ++ "X"
  println(acc)

Am I supposed to build a list first? Maybe using constructor contexts?

I tried to write a small function (as an exercise) that converts a list<a> with ?show: a -> string into a string that contains the stringified values of the list, separated by commas (without using joinsep/join or map, but doing it manually, only using concat/join for the final step).

This is my (rather unwieldy) code:

pub fun csv( entries : list<a>, ?show : a -> string ) : string
  fun build ( acc : ctx<list<string>>, l : list<_> ) : ctx<list<string>>
    match l
      Cons(x, xx) -> (acc ++ ctx Cons(",",Cons(x.show,hole))).build(xx)
      Nil -> acc
  match entries
    Nil -> ""
    Cons(x, xx) -> (build(ctx Cons(x.show,hole), xx) ++. Nil).join

pub fun main()
  println([1,2,3].csv)

Some questions:

• It doesn't feel idiomatic, considering how much code it is. What am I doing "wrong"? How to make it shorter (without using joinsep/join)?
• What is the (or a) proper name for the build function?
• Is it possible to use the type a from the outer function declaration, and refer to it in the inner function declaration? If I write fun build ( acc : ctx<list<string>>, l : list<a> ) : ctx<list<string>>, then this a will refer to a new polymorphic type, not the existing one from the outer function.
• Is it okay to use a more procedural approach in Koka when "building" strings? If yes, how to do it and what should I look out for?

[JanBeh]

• Is it possible to use the type a from the outer function declaration, and refer to it in the inner function declaration? […]

I found this post on the web, where Tim Cuthbertson writes regarding Koka:

You can’t refer to generic type parameters in the function body

[…] type parameters in the function type are not bound in the function body. So this annotation (of val result) is incorrect:

fun singleton<a>(value: a): list<a>
  val result: list<a> = [value]
  result

The problem here is that a in the function signature can’t be referenced in the function body. […]

I wonder if there is some way to work around this, maybe with an explicit forall? I also don't quite understand the forall (and maybe exists and some?) syntax yet.

I noticed I can write:

pub fun csv<element>( entries : list<element>, ?show : element -> string ) : string

but this also doesn't bind element inside the function body, i.e. the following does not work then:

  fun build( acc : ctx<list<string>>, l : list<element> ) : ctx<list<string>>

and gives me:

kind error: Type element is not defined
   hint: bind the variable using forall<element> ?

I assume this is just not possible? Or is there a way?

[timbertson]

Hello 👋

To workaround the issue I pointed out there, usually you can just remove some explicit types from within the function body.

E.g. when you'd like to write build, I think you have a few choices:

• don't annotate the argument types at all, koka is pretty good at figuring it out
• build could be generic? i.e build<element> or use e instead of element

Unfortunately because you can't (AFAIK) tell the compiler that this generic type is only ever the same as element, it'll mean you need to pass through show to satisfy the generics - i.e. build(acc, l, ?show). Since l's element type will match the type of the show function you have available, this will work.

Here's a working version (I removed ctx just to keep the types simple):

pub fun csv<element>( entries : list<element>, ?show : element -> string ) : string
  fun build( acc : list<string>, l : list<e>, ?show: e -> string) : list<string>
    l.map(show)
  build([], entries).join(",")

[timbertson]

As for the efficient string building, there's a couple of issues around this already:

• Support string interpolation #122
• String Interpolation #528

tl;dr I don't think there's anything more efficient you can do right now, but there are ideas in the works.

[JanBeh]

it'll mean you need to pass through show to satisfy the generics

Actually I had that variant first, but then thought I could write it more concise (without passing show around), which is why I ran into the described problem.

But perhaps just omitting the type annotations is fine in those cases.

As for the efficient string building, there's a couple of issues around this already:

• Support string interpolation #122
• String Interpolation #528

Those issues seem to target something like "format strings" or "string templates". But that's not what I meant. What I meant is some sort of mutable data structure where I can efficiently append (not necessarily insert) strings with reasonable efficiency. In Java, for example, that would be a StringBuffer.

I tried writing one (actually two variants) in Koka, using first-class constructor contexts, hoping that "appending" will be efficient then:

// Variant 1: string buffer based on a list of chars

alias strbuf1 = ctx<list<char>>

val empty1 : strbuf1 = ctx hole

pub fun char/append1( buf : strbuf1, c : char ) : strbuf1
  buf ++ ctx Cons(c,hole)

pub fun list-char/append1( buf : strbuf1, cs : list<char> ) : strbuf1
  match cs
    Nil -> buf
    Cons(c,cc) -> buf.append1(c).append1(cc)

pub fun string/append1( buf : strbuf1, s : string ) : strbuf1
  buf.append1(list(s))

pub fun finalize1( buf : strbuf1 ) : string
  (buf ++. Nil).string


// Variant 2: string buffer based on a list of strings

alias strbuf2 = ctx<list<string>>

val empty2 : strbuf2 = ctx hole

pub fun append2( buf : strbuf2, s : string ) : strbuf2
  // easier to append
  buf ++ ctx Cons(s,hole)

pub fun finalize2( buf : strbuf2 ) : string
  // but requires join to finalize
  (buf ++. Nil).join

With those string buffers (strbuf1 or strbuf2), I can rewrite my csv function in a more procedural (and in my opinion easier to read) way:

// Both variant 1 and variant 2 can be used in the same way.
// Below demonstrated with variant 1, but variant 2 works same:

pub fun list-string/csv1( l : list<string> ) : string
  match l
    Nil -> ""
    Cons(first, remaining) ->
      var buf := empty1.append1(first)
      remaining.foreach fn (element)
        buf := buf.append1(",")
        buf := buf.append1(element)
      buf.finalize1

pub fun list-show/csv1( l : list<a>, ?show : a -> string ) : string
  list-string/csv1(l.map(show))

pub fun main()
  println([1,2,3].csv1)

Note that I deliberately refrained from using existing functions like intersperse for the sake of having an example problem to solve.

Now what I wonder:

• Which variant is more efficient and/or more idiomatic: strbuf1 or strbuf2? Or are both approaches a bad idea?
• Is there already something existent in the standard library that acts like such a string buffer?
• Is it costly to convert a list<string> to a single string using join?
• And how about the costs of converting a string to a list<char> and vice versa using std/core/string/list and std/core/string/listchar/string, respectively?
• Is the memory representation of a list<char> much bigger than the representation of a string?

Answers to these questions might help me to understand how to deal best with strings in Koka in cases where I do not just pass them but need to "build" them somehow.

[TimWhiting]

There is not something currently in the standard library that acts like a string buffer, but I think the regular string functions are pretty performant for most use cases currently. I believe they try to realloc before mallocing new memory for most operations, which saves time for copying and allocation. join for example iterates over the list, calculating the total size before allocating space for the new string.

As a general rule working with string will be much faster than converting between strings and list<char>, at least when you are working with large strings.

With string building I would expect that list<string> would be fastest, with a final join().

Yes, the list<char> will be take at least twice the space of string probably.

[JanBeh]

To answer my questions, I did some benchmarks:

pub fun bm0()
  var buf := ""
  for(1,10000) fn(_)
    buf := buf ++ "PARIS " // concatenating plain strings
  buf.keep.ignore

pub fun bm1()
  var buf := empty1
  for(1,10000) fn(_)
    buf := buf.append1("PARIS ") // using `strbuf1` based on `ctx<list<char>>`
  buf.finalize1.keep.ignore

pub fun bm2()
  var buf := empty2
  for(1,10000) fn(_)
    buf := buf.append2("PARIS ") // using `strbuf2` based on `ctx<list<string>>`
  buf.finalize2.keep.ignore

Without really using any sophisticated benchmarking framework, I did three measurements on my machine and calculated the median.

• bm0 0.01s
• bm1 27.78s
• bm2 5.00s

This looked like I should just work with strings and not worry. But then I increased the iterations from 10000 to 30000 and got thse timings:

• bm0-triple 0.12s
• bm1-triple 247.99s (about 3² = 9 times longer than with 1/3 of the iterations)
• bm2-triple 45.32s (about 3² = 9 times longer than with 1/3 of the iterations)

At least bm1 and bm2 seem to show quadratic behavior with regard to the iteration count, which is not what I expected. 🙁 I would like to understand what's the problem here. Is it impossible to do some of these operations "in-place"? Or does something prohibit it?

I tried adding the fip statement to append2 to get some information on whether in-place operation can take place:

alias strbuf2 = ctx<list<string>>

pub fip fun append2( buf : strbuf2, s : string ) : strbuf2
  buf ++ ctx Cons(s,hole)

And I got:

warning: fip fun append2: function allocates at most 1 but was declared as allocating nothing

I guess that's because a new Cons is created?

Finally, I was able to declare list-char/append1 as fip by writing it as follows:

pub fip fun list-char/append1( buf : strbuf1, cs : list<char> ) : strbuf1
  match cs
    Nil -> buf
    Cons(c,cc) -> (buf ++ ctx Cons(c,hole)).append1(cc)

But this reduced execution time from 27.78s to 26.85s only (if that's even a significant change).

[TimWhiting]

fip can take a parameter telling how many structures it is expected to allocate. Here that would be 1 for the Cons cell: fip(1) ....

Constructors contexts are more performant if used in a functional manner. Currently local variables keep an extra reference even when the right hand side could reuse the memory, which make them a lot less performant, especially for something like a long list: PR #716, should help, I should benchmark this with that and see how much the benchmarks change.

[JanBeh]

I found a solution that works pretty fast:

alias strbuf3 = list<string>

val empty3 : strbuf3 = Nil

pub fun append3( buf : strbuf3, s : string ) : strbuf3
  Cons(s,buf)

pub fun finalize3( buf : strbuf3 ) : string
  buf.reverse-join

But what I don't understand is why this is so much faster than the first-class constructor contexts used in strbuf2 (from my previous post). Isn't the point of constructor contexts to avoid the final reversal, like explained here?

What am I missing (or misunderstanding)?

[TimWhiting]

Answered above. I would expect #716 to make constructor contexts a ton faster for mutable variables. It should be equivalent to the functional version then.

[TimWhiting]

There is a lot to unpack here, I'm going to also mention PR #607, which delays the show / string building until the full string is actually needed - if it is never used you don't pay the cost of appending, and if it is being printed to the console you can let the OS do the buffering potentially if wanted. As another general comment, we will probably be looking at this soon while we are working on libuv, which will probably require something similar, but for bytes: #652.

[JanBeh]

Thanks @TimWhiting for your feedback, information, and referring to the open issues. I'll answer in a single post here.

I would expect #716 to make constructor contexts a ton faster for mutable variables. It should be equivalent to the functional version then.

Okay, then it's an issue of Koka. I will be looking out for it and want to practice functional style programming anyway for now. 😉 But as you can see further below, even in functional context, constructor contexts seem to impose some penalty as of now.

There is not something currently in the standard library that acts like a string buffer, but I think the regular string functions are pretty performant for most use cases currently. […]

I think that depends on usage. For example plain string concatenation using (++) : ( x : string, y : string ) -> string is generally fast, but turns out even slower than using ctx<list<char>> when circumventing the issues with local variables.

I added a strbuf0 as a plain wrapper for string concatenation using ++:

alias strbuf0 = string

val empty0 : strbuf0 = ""

pub fun append0( buf : strbuf0, s : string ) : strbuf0
  buf ++ s

pub fun finalize0( buf : strbuf0 ) : string
  buf

And put together a program to benchmark all variants, while commenting out the combinations that trigger the issues with local variables and thus are catastrophically slow:

Code

import std/time


// Working directly with strings by appending:

alias strbuf0 = string

val empty0 : strbuf0 = ""

pub fun append0( buf : strbuf0, s : string ) : strbuf0
  buf ++ s

pub fun finalize0( buf : strbuf0 ) : string
  buf


// List of chars, using constructor contexts:

alias strbuf1 = ctx<list<char>>

val empty1 : strbuf1 = ctx hole

pub fun char/append1( buf : strbuf1, c : char ) : strbuf1
  buf ++ ctx Cons(c,hole)

pub fun list-char/append1( buf : strbuf1, cs : list<char> ) : strbuf1
  match cs
    Nil -> buf
    Cons(c,cc) -> buf.append1(c).append1(cc)

pub fun string/append1( buf : strbuf1, s : string ) : strbuf1
  buf.append1(list(s))

pub fun finalize1( buf : strbuf1 ) : string
  (buf ++. Nil).string


// List of strings, using constructor contexts

alias strbuf2 = ctx<list<string>>

val empty2 : strbuf2 = ctx hole

pub fun append2( buf : strbuf2, s : string ) : strbuf2
  buf ++ ctx Cons(s,hole)

pub fun finalize2( buf : strbuf2 ) : string
  (buf ++. Nil).join


// List of strings, using final reversing:

alias strbuf3 = list<string>

val empty3 : strbuf3 = Nil

pub fun append3( buf : strbuf3, s : string ) : strbuf3
  Cons(s,buf)

pub fun finalize3( buf : strbuf3 ) : string
  buf.reverse-join


// Using local variables:

pub fun bm-localvar(count, empty, append, finalize)
  var buf := empty
  for(1,count) fn(_)
    buf := buf.append("PARIS ")
  buf.finalize.keep.ignore

pub fun bm-localvar0(count) bm-localvar(count, empty0, append0, finalize0)
pub fun bm-localvar1(count) bm-localvar(count, empty1, append1, finalize1)
pub fun bm-localvar2(count) bm-localvar(count, empty2, append2, finalize2)
pub fun bm-localvar3(count) bm-localvar(count, empty3, append3, finalize3)


// Without local variables, but functional:

pub fun bm-functional(count, empty, append, finalize)
  fun func(remaining, buf)
    if ( remaining <= 0 ) then return buf
    func(remaining - 1, buf.append("PARIS "))
  func(count, empty).finalize.keep.ignore

pub fun bm-functional0(count) bm-functional(count, empty0, append0, finalize0)
pub fun bm-functional1(count) bm-functional(count, empty1, append1, finalize1)
pub fun bm-functional2(count) bm-functional(count, empty2, append2, finalize2)
pub fun bm-functional3(count) bm-functional(count, empty3, append3, finalize3)


// Execute single benchmark multiple times:

pub fun benchmark(bm-func)
  val start = now-in()
  bm-func()
  val end = now-in()
  end - start


// Execute benchmarks:

pub fun benchmarks( count : int )
  println("functional0: " ++ show(benchmark{bm-functional0(count)}))
  println("functional1: " ++ show(benchmark{bm-functional1(count)}))
  println("functional2: " ++ show(benchmark{bm-functional2(count)}))
  println("functional3: " ++ show(benchmark{bm-functional3(count)}))
  println("localvar0: " ++ show(benchmark{bm-localvar0(count)}))
  //println("localvar1: " ++ show(benchmark{bm-localvar1(count)}))
  //println("localvar2: " ++ show(benchmark{bm-localvar2(count)}))
  println("localvar3: " ++ show(benchmark{bm-localvar3(count)}))

pub fun main()
  benchmarks(100000)
  println("Double:")
  benchmarks(200000)

These are the results on my machine (three runs, manually taking the median, each):

functional0: 3.440947597s
functional1: 0.124981684s
functional2: 0.02572074s 
functional3: 0.016868231s
localvar0: 3.481164959s
localvar3: 0.026768351s
Double:
functional0: 13.919106149s
functional1: 0.243395065s
functional2: 0.050051179s
functional3: 0.033231439s
localvar0: 13.757575816s
localvar3: 0.053887991s

As you can see, list<char> (used by strbuf1) clearly outperforms string concatenation using ++ when the count is big enough. I wonder if it's possible to make "appending a string to a string" asymptotically the same fast as appending a list<char> to a list<char> ctx<list<char>>?

Whether that's possible or not may depend on the internal representation of strings, which I don't know about. Edit: Maybe it's not possible without overhead allocation.

Also interesting is that even in the functional case, there seem to be some slowdown when using constructor contexts (compare functional2 to functional3, i.e. strbuf2 and strbuf3). Here, no local variables are used, but there is still some penalty imposed on strbuf2, and I wonder where it comes from. Using constructor contexts seems to be almost twice as slow. At least there doesn't seem to be an asymptotical penalty anymore, but I thought constructor contexts were meant to make things faster, not slower.

As another general comment, we will probably be looking at this soon while we are working on libuv, which will probably require something similar, but for bytes: #652.

After having loved Unicode in the beginning, I'm meanwhile more fond of treating strings as "opaque" sequences of (8 bit) bytes (like done in Lua or done in Zig). That is because the notion of a Unicode codepoint isn't much useful anyway, considering the complex rules of Unicode text segmentation, specifically regarding grapheme cluster boundaries. (Also consider Rust's weird OsString, which uses WTF-8 encoding on Windows, AFAIK.) But I can understand if Koka wants to stick to the concept of (Unicode) codepoints. I wonder if that has certain performance drawbacks though. Again, it would be nice if operations with string would at least asymptotically be same efficient as operations with list<char>.

[TimWhiting]

Try compiling with -O2 for performance comparisons.

[JanBeh]

Oh, sorry, I didn't think on -O2. This is with optimizations enabled (on same machine, same substring count as above):

functional0: 2.19402386s
functional1: 0.011919917s
functional2: 0.002923932s
functional3: 0.002915747s
localvar0: 2.208205781s
localvar3: 0.003862158s
Double:
functional0: 9.555880409s
functional1: 0.025726073s
functional2: 0.005730163s
functional3: 0.005868332s
localvar0: 9.152665955s
localvar3: 0.007863365s

So functional2 and functional3 seem to be same fast now (as to be expected). But localvar1 and localvar2 are still very slow (probably due to the issue you mentioned), as you can see in the following benchmark with a lower count (20000 substrings instead of 100000 and 200000, but also using -O2):

functional0: 0.021141885s
functional1: 0.002156075s
functional2: 0.000583001s
functional3: 0.000590866s
localvar0: 0.021044472s
localvar1: 15.972498712s
localvar2: 3.251997618s
localvar3: 0.000757528s

[JanBeh]

For anyone who has the same problem and just wants a quick solution: This is what I now do "from scratch" when needed:

pub fun main() : string
  var strbuf := Nil
  fun put( s : string ) strbuf := Cons( s, strbuf )

  put("Hello ")
  put("World!")
  // and so on

  strbuf.reverse-join()

Of course one could define a type alias and a free standing function, but the above code snippet seems to be reasonable in most cases.

[TimWhiting]

As a quick experiment, I increased the number of iterations to 10000000 and tested a few other languages.

Koka:

functional2: 0.294661s
functional3: 0.29737s
localvar2: 0.339827s
localvar3: 0.308172s

Dart is 2.2x faster (using StringBuffer)

void main(List<String> arguments) {
  final strBuff = StringBuffer();
  for (int i = 0; i < 10000000; i++) {
    strBuff.write("PARIS ");
  }
  strBuff.toString();
  print("Done");
}

time ./bin/strbuff.exe 
Done
./bin/strbuff.exe  0.12s user 0.02s system 95% cpu 0.143 total

Scala is 1.7x faster using Scala Native (using StringBuilder/Builder).

@main
def main(): Unit =
  val x = StringBuffer()
  for (i <- 0 until 10000000) {
    x.append("PARIS ")
  }
  x.toString()
  println("Done")
  ()
 
@main
def main2(): Unit =
  val x = StringBuilder()
  for (i <- 0 until 10000000) {
    x ++= "PARIS "
  }
  x.toString()
  println("Done")
  ()

time ./xx (native/builder)
Done
./xx  0.16s user 0.04s system 99% cpu 0.194 total

C++ is ~3x faster (using String +=).

#include <iostream>
#include <string>

int main(int argc, char *argv[])
{
    std::string str = "";
    for (int i = 0; i < 10000000; i++)
    {
        str += "PARIS ";
    }
    std::cout << "Done" << std::endl;
}

time ./x
Done
./x  0.08s user 0.01s system 95% cpu 0.094 total

At this point (after #716), I don't think it is the local variables that are holding it back, but other aspects of this, such as using resizable vectors instead of lists, etc. For example, turning the list into a vector before joining the bytes costs 1/3 of the time. Allocating Cons cells for the list also takes time. There are obviously things that we can do for this microbenchmark to make it faster (allocating the whole vector ahead of time since we know the size), but I don't feel like that would be indicative of performance in general. A better solution would probably be to have ctx<list<vector<string>>> with efficient concatenation of a list of vectors, and reasonable vector sizes. I think we could get faster than Dart this way, and possibly within 10% of C.

[JanBeh]

To be fair, it might make sense to also look at memory consumption in addition to execution time. I would assume that implementations that pre-allocate more memory that might actually stay unused can reach a faster execution time by principle. Maybe a language or an algorithm that appears faster has a higher memory use.

[TimWhiting]

True.

I also think that building strings this large is probably rare, and this won't probably be the area that most apps see their biggest performance hit. But still, we'd like to have a good builtin string buffer at some point.

I think that resizable vectors e.g. vector<string> (by doubling + copy) which is probably what most other languages do (except at the level of chars) is probably memory inefficient at some point, and each copy incurs some overhead. I think what I mentioned ctx<list<vector<string>>> with each vector being a constant size (e.g. 100? - though probably want something so the total vector is cache-aligned if we are really going for performance), and maybe keeping a total char length or total vector length along the side, could allow us to only allocate the final char vector once, without memory/copy penalties for intermediate/resized arrays. This could potentially even outperform the default implementation in other languages - due to the intermediate copy avoidance.

[TimWhiting]

I found an issue with static strings not actually being static causing a lot of allocation / deallocation.
Lifting the static string to a noinline val shaves 1/3 off the runtime in general.

localvar5 uses my suggestion of ctx<list<vector<string>>>, localvar4 uses list<vector<string>> + reverse.

with vector size 100 we outperform my naive C++

functional2: 0.195837s
functional3: 0.194424s
functional4: 0.079787s
functional5: 0.078314s
localvar2: 0.230214s
localvar3: 0.196078s
localvar4: 0.094924s
localvar5: 0.093777s

100 also seems to be a sweet spot for the size of each vector.

It starts being worth the additional constant size / space overhead at around 40 appends I think. Below that they all wash out in noise.

[TimWhiting]

Full code for reference:
https://github.com/TimWhiting/koka/blob/335274c53ae106a209e0cf4880b5cae2a8c25964/test/cgen/string-buf.kk
This is on the #762 branch.