Speeding up the conversion of flvectors to string

[Alessandro Motta]

Hi racket-users!

I've recently become interested in Lisp/Scheme and have started to hack
in Racket. The excellent documentation, the fast integrated search, and
DrRacket have made that a real pleasure.

Thank you for that!

I've been working on a tool to convert notes from the reMarkable 2
tablet to SVG files. At the core is the conversion of (x, y) coordinate
pairs from two `flvector`s to a string of the form "x1,y1 x2,y2 x3,y3".

```
(define (xy->string x y)
(string-append
(~r x #:precision 1) ","
(~r y #:precision 1)))

(define (xy-vectors->string x-vec y-vec)
(for/fold ((coordinates "")
(separator "")
#:result coordinates)
((x (in-flvector x-vec))
(y (in-flvector y-vec)))
(values (string-append
coordinates
separator
(xy->string x y))
" ")))
```

This is currently the bottleneck for large conversion jobs.

Profiling these functions with `profile-flame-graph` resulted in
https://gist.githubusercontent.com/amotta/cfe4b19e24455af219521c9e94455c67/raw/dbbc87bd2f6dd4e27c33831749baa90fffdaed55/flvector-to-coordinates-string-flamegraph.svg

The full profiling script is available at
https://gist.github.com/amotta/e76197082bb1bf63538ede01872917f3

Roughly 90% of time is spent in `contract/private/arrow-val-first.rkt`.
Based on my very limited understanding of Racket, it seems that ~38% of
time is spent handling keyword arguments (presumably `#:precision 1`?).
The `catnp` function (the conversion from flonum to string, I think)
takes up only ~11% of time.

Is this interpretation of the flame graph correct? If so, are there any
obvious blunders on my part? Any ideas for how to speed up this code?


Best wishes,
Alessandro

[Bogdan Popa]

Hi Alessandro,

Here is a version of your program that is about 30 times faster on my
machine (9s -> 300ms):

#lang racket/base

(require racket/flonum
racket/format
racket/port)

(define (xy-vectors->string x-vec y-vec)

(call-with-output-string
(lambda (out)
(for ([i (in-naturals)]
[x (in-flvector x-vec)]
[y (in-flvector y-vec)])
(unless (zero? i)
(write-char #\space out))
(write-string (~r x #:precision 1) out)
(write-char #\, out)
(write-string (~r y #:precision 1) out)))))

(time
(let ([x (make-flvector 100000)]
[y (make-flvector 100000)])
(xy-vectors->string x y)))

All the calls to `string-append` in your original program end up
allocating larger and larger strings and then immediately discarding
them on subsequent iterations, which is costly over many iterations.

Hope that helps,
Bogdan

[Jens Axel Søgaard]

As Bogdan writes, the problem is repeatedly calling `string-append`.
Instead one can make a list of all the small strings and then use `string-join` at the end.

#lang racket
(require racket/flonum)

(define (xy->string x y)
  (string-append
   (~r x #:precision 1) ","
   (~r y #:precision 1)))

(define (xy-vectors->strings x-vec y-vec)
  (for/list ((x (in-flvector x-vec))
             (y (in-flvector y-vec)))
    (xy->string x y)))

(define (xy-vectors->string x-vec y-vec)

  (string-join (xy-vectors->strings x-vec y-vec) " "))

--
You received this message because you are subscribed to the Google Groups "Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to racket-users...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/0139e84f-be70-2bb8-14ac-0159915e7681%40gmail.com.

--

--
Jens Axel Søgaard

[Bogdan Popa]

I forgot to mention this earlier, but it might be enlightening to
run the two versions of the program with the `PLTSTDERR` environment
variable set to "error debug@GC" to see GC debug messages. For example:

env PLTSTDERR='error debug@GC' racket flvector-to-coordinates-string.rkt >/dev/null

[Robby Findler]

Replacing ` (~r x #:precision 1)` with `(number->string x)` and ditto for `y` eliminates the overhead of contracts and brings about another 4x speedup on my machine.

That may not work, tho, depending on Alessandro's original usecase, since the strings are different.

I was also going to, as Bogdan does, recommend ports. In other languages, strings are a sophisticated data structure, but in Racket they are just linear arrays. The ports abstraction is the best place to situate streaming stuff (especially if you're going to write the result to a file in the end). String and byte ports are great for unit testing too -- you can just drop in a file port in the same place for the real code, minimizing the amount of code you need that's only for testing.

Robby

--
You received this message because you are subscribed to the Google Groups "Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to racket-users...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/m2v95zcs9v.fsf%40defn.io.

[Alessandro Motta]

Thank you all for these quick and helpful responses!

I've noticed the `call-with-output-string` mechanism while browsing
various Racket code bases, but was under the impression that this is
"just" a convenient abstraction over strings. Based on Bogdan's code and
Robby's explanation, it's now clear that this thinking was wrong.

I also like Jens' code for its pure functional elegance. I'm surprised
that building up a long list of short strings before joining them is so
much faster. After all, isn't the final `string-join` essentially doing
what the original code snipped did? (Clearly not! I will have a look at
the implementation.)

So, it seems that my intuitions about the costs of various operations
were completely off here. Thank you for pointing this out. Tracking GC
overheads by setting `PLTSTDERR` is very helpful in this regard.

Off topic: I've enjoyed your "Racket hacking" screencasts, Bogdan! It's
helpful to see how hacking on real world Racket code bases can look like.


Best wishes,
Alessandro

> <mailto:racket-users%2Bunsu...@googlegroups.com>.

> To view this discussion on the web visit
> https://groups.google.com/d/msgid/racket-users/m2v95zcs9v.fsf%40defn.io

> <https://groups.google.com/d/msgid/racket-users/m2v95zcs9v.fsf%40defn.io>.
>

[Robby Findler]

On Sun, Jun 27, 2021 at 11:58 AM Alessandro Motta <amot...@gmail.com> wrote:

I also like Jens' code for its pure functional elegance. I'm surprised
that building up a long list of short strings before joining them is so
much faster. After all, isn't the final `string-join` essentially doing
what the original code snipped did? (Clearly not! I will have a look at
the implementation.)

 

This is a classic O(n^2) gotcha. Cons is constant work (in terms of the size of its inputs) and string-append is linear in the size of all of its arguments. So if you repeatedly string-append in a loop, you'll get the 1+2+3+4+5+6+7+8+....+n which is O(n^2), but if you collect all the arguments in a list and then call string-append once at the end, it will be linear (which implies than string-append isn't naive when it gets a lot of arguments; it looks at them twice. Once to know how much to allocate before a second pass to filling in the string).

hth,

Robby

[Jens Axel Søgaard]

Den søn. 27. jun. 2021 kl. 18.58 skrev Alessandro Motta <amot...@gmail.com>:

I also like Jens' code for its pure functional elegance. I'm surprised
that building up a long list of short strings before joining them is so
much faster. After all, isn't the final `string-join` essentially doing
what the original code snipped did? (Clearly not! I will have a look at
the implementation.)

The following is the same answer as Robby's, but fills in some details.
I wrote this mainly because I couldn't find a web-page with the explanation.

Let's say we have two strings a and b of lengths m and n respectively.

How much work must  (string-append a b) do?

Conceptually the following steps need to be done:
  1. Allocate a new string c of length m+n.
  2. Copy the string a into c.
  3. Copy the string b into c.

This means that the time (work) needed to append the strings a and b are proportional to m+n.

How much work is done here?

    (string-append "x" (string-append "y" (string-append "z" ""))) 

First (string-append "z" "w") takes time 1+0=1 with the result "z".
Then (string-append "y" (string-append "z" "")) or  (string-append "y" "z") takes time 1+1=2 with the result "yz".
Then (string-append "x" (string-append "y" (string-append "z" ""))) or (string-append "x" "yz") takes time 1+2 = 3 with result "xyz".
In total we have used time 1+2+3 =6.

We see that if we 3 times use string-append to add strings of length 1, then we use time 1+2+3=6.
In general, if we n times use string-append to add strings of length 1, then we use time 1+2+3+...+n.
The last sum is more or less n^2.  See [1].

The same thing happens in your loop, where you repeatedly use string-append to append a small string.
The length of the small string is no longer 1, but the same happens - and the time used by the
loop is proportional to n^2.


Now suppose we have a list of the strings to append
    (list "x" "y" "z")
and we need to append them. How much work is there now?

Well, first we can calculate the length of the result 1+1+1 = 3.
Then we allocate a new string of length 3. Then each individual
string is copied and that takes time 1+1+1=3. 

Here, each string is only copied once. For comparison in the loop version
the string z is copied multiple times. 


But wait - why does a loop that uses cons multiple times to build up
a list not have the same problem?

Because in (cons x xs) the existing list xs isn't copied.
The steps are 
   1. a new pair with two cells  (the car and the cdr) are allocated
   2. the contents of the car is set to x
   3. the contents of the cdr is set to xs.

This always takes the same amount of time, no matter how long the list xs is.
This means that the time used by cons is constant (that is, proportional to 1).

Note: This phenomenon that using string-append in a loop is not a Racket only problem.
          It is a common pitfall in many languages. 



[1] Remember the famous story of Gauss as a child that calculated 1+2+...1000 ? 
     https://www.youtube.com/watch?v=Dd81F6-Ar_0


/Jens Axel  -  https://racket-stories.com






 

[Bogdan Popa]

While I think the complexity piece is important, I feel like it's worth
pointing out just how much more expensive the allocation -- and its
ramifications, like the resulting GC pressure and CPU cache misses -- is
than one might think. Here's a quadratic version of the code that
avoids allocations:

#lang racket

(require racket/flonum)

(define (xy->string x y)
(string-append
(~r x #:precision 1) ","
(~r y #:precision 1)))

(define len 0)
(define dst (make-string 5000000))
(define (string-append! b)
(string-copy! dst 0 dst 0 len) ;; intentionally performing pointless work to be n^2
(string-copy! dst len b)
(set! len (+ len (string-length b))))

(define (xy-vectors->string x-vec y-vec)

(for ((x (in-flvector x-vec))
(y (in-flvector y-vec)))
(string-append! (xy->string x y))
(string-append! " ")))

(time
(let ([x (make-flvector 100000)]
[y (make-flvector 100000)])
(xy-vectors->string x y)))

On my machine (running Racket CS 8.1), this is faster than the
`call-with-output-string` version I posted earlier by about 50ms.

[jackh...@gmail.com]

Anyone got an implementation of a mutable StringBuilder-like object? I could use it in Rebellion's implementation of `into-string` which currently isn't quadratic, but it definitely has the allocation problem.

[Matthew Flatt]

At Sun, 27 Jun 2021 21:36:09 +0300, Bogdan Popa wrote:
> While I think the complexity piece is important, I feel like it's worth
> pointing out just how much more expensive the allocation -- and its
> ramifications, like the resulting GC pressure and CPU cache misses -- is
> than one might think. Here's a quadratic version of the code that
> avoids allocations:

> [...]

> On my machine (running Racket CS 8.1), this is faster than the
> `call-with-output-string` version I posted earlier by about 50ms.

That doesn't sound right to me.

Your program does run fast on my machine, but I think it's because this
line doesn't have the intended bad effect:

> (string-copy! dst 0 dst 0 len) ;; intentionally performing pointless
> ;; work to be n^2

A `string-copy!` like this will eventually use the C library's
`memmove`, which apparently (and sensibly) doesn't do anything if the
source and destination are the same. Try copying to a `dst2` to get
quadratic behavior.

[Bogdan Popa]

Ah! You're right. When I make the change you suggest, the program
takes 5s to run. Filed under "Accidentally Not Quadratic" 😅.

[Bogdan Popa]

Bogdan Popa writes:

> Ah! You're right. When I make the change you suggest, the program
> takes 5s to run. Filed under "Accidentally Not Quadratic" 😅.

The program actually takes 2.5s to run. I missed the fact that I had
made two separate calls to `string-append!` in that version of the
program because the `string-append!` where the source and the
destination were the same ended up being so cheap. The fixed version:

https://gist.github.com/Bogdanp/f36201cd852ac2e363fdaebba1d02709#file-quadratic-no-alloc-rkt

I also wrote a version of that same code with a custom `string-append`
function:

https://gist.github.com/Bogdanp/f36201cd852ac2e363fdaebba1d02709#file-quadratic-with-alloc-rkt

That version takes about 6.7s to run. When I did that, I finally
realized that what I had misinterpreted as allocation overhead was
actually mostly the overhead of zero-filling the newly-allocated string,
which I'd forgotten about.

Here's that same code, but using bytes instead of strings:

https://gist.github.com/Bogdanp/f36201cd852ac2e363fdaebba1d02709#file-quadratic-with-alloc-bytes-rkt

It runs in 2.2s. Finally, a version of that code that uses a custom
byte string implementation that doesn't perform an initialization step:

https://gist.github.com/Bogdanp/f36201cd852ac2e363fdaebba1d02709#file-quadratic-with-alloc-no-fill-rkt

That runs in 870ms, which is a little under half the time of the
previous version, which makes sense to me since the number of iterations
is halved and the GC is being side-stepped.

All that to say I was completely wrong yesterday about allocation being
a big factor here!

Assuming I haven't made any other mistakes and the same 2x improvement
could apply to a version of `string-append` that doesn't try to fill the
newly-allocated string before copying, I wonder if that would be a
worthwhile improvement to make to it.

[Alessandro Motta]

Thank you for these explanations, Robby and Jens! The parenthetical
remarks about the two-pass approach of `string-append` were particularly
helpful. That makes sense now.

One thing that is still puzzling / worrying me: I completely failed to
identify the actual bottleneck when profiling the code.

Did I simply misinterpret the profiling output / flame graph? Or is the
problem rather that memory allocations and garbage collection are not
tracked by the profiler?

Thinking about it: Does garbage collection also pause the profiler's
sampler thread? That would explain the lack of samples from these code
paths, of course.


All the best,
Alessandro

[Robby Findler]

I think you found a slowdown that's just a severe as the one we've been talking about and, once that one'd been cleared up, you might have seen the other one, perhaps in the calls to string-append. But you are right that some costs (like gc) are smeared out across the whole computation and thus hard to identify with profiling (hence Bogdan's helpful hint about gc logging).

Robby

[Jonathan Simpson]

On Sunday, June 27, 2021 at 10:29:55 AM UTC-4 Robby Findler wrote:

Replacing ` (~r x #:precision 1)` with `(number->string x)` and ditto for `y` eliminates the overhead of contracts and brings about another 4x speedup on my machine.

This is because the compiler is able to remove the contract checks, not because number->string doesn't have a contract, correct? If it is the compiler, is there any rule of thumb to determine when the compiler will likely remove the contract checks? Using typed 'for' iterators seems to be one case that the compiler optimizes, but can we rely on others?

Thanks,

Jonathan

[Sam Tobin-Hochstadt]

There are two possible meanings for "contract checks" here. One is
"does it check that it gets the right kind of arguments, and raise an
error if not". In that sense, every function that is not "unsafe" has
contracts, certainly including `number->string`. The other meaning is
"uses the `racket/contract` library". The `~r` function has a contract
in that sense, while `number->string` does not, and that's a
significant source of overhead. On my laptop, just removing the
contract on `~r` in the source of the `racket/format` library speeds
up Bogdan's revised program from 600ms to 200ms.

Most of the time, the compiler does not remove either kind of contract
check. Sometimes the first kind of contract check can be removed in
the simplest of cases; the second kind is basically never removed by
the compiler. There are other cases where macros can generate code
that omits contract checks, as with the `for` forms when used with
sequence generators like `in-list`, but that is again for simple
checks.

Sam

[Stefan Schwarzer]

On 2021-06-28 21:18, Alessandro Motta wrote:> One thing that is still puzzling / worrying me: I completely failed to

> identify the actual bottleneck when profiling the code.
>
> Did I simply misinterpret the profiling output / flame graph? Or is the
> problem rather that memory allocations and garbage collection are not
> tracked by the profiler?

Some things that might help (at least they helped me :-) ) ...

- Use the `profile-thunk` function described at
https://docs.racket-lang.org/profile/ (most likely that's
how you got your profile data to begin with).

- Use the `errortrace` option, i. e. run the instrumented
program with `racket -l errortrace -t program.rkt`. The
errortrace functionality is described as:

When using Errortrace, profiles are more precise and
more fine-grained (expression-level instead of
function-level) but profiling has higher overhead and
recompilation may be necessary.

- Note the remark about recompilation. It took me a bit to
realize that I had to delete the `.zo` files. :-) In
practice, I remove the `compiled` folders for the program
I want to run. If you don't remove the compiled code, the
old code - without errortrace information - will be used,
but as far as I remember you'll get no error message or
warning.

- There's also an option for the sample interval, so you can
lower it to get finer-grained measurements. I don't find
this now. Maybe someone else can point to more
information.

- Learn to read the text output of the profiler as described
under
https://docs.racket-lang.org/profile/#%28part._.Textual_.Rendering%29
Especially the distinction between the times with and
without calls to nested functions is helpful. The profiler
output may seem a bit overwhelming first, but with some
time and experimentation it becomes better (like with so
many things regarding Racket ;-) ).

Stefan

[Jonathan Simpson]

On Monday, June 28, 2021 at 10:25:36 PM UTC-4 Sam Tobin-Hochstadt wrote:

Thanks for the reply. I was under the impression that all of the racket provided functions had full racket/contract contracts implemented at the module boundary, which is what I thought was generating errors of the form:

---

(number->string "aa")

; number->string: contract violation

;   expected: number?

;   given: "aa"

---

I take it that the contract error above was generated by a lower-level contract then. I've only glanced at contracts, so I assume this is documented somewhere. Is this section of the Reference referring to the simple contracts that you mention? From https://docs.racket-lang.org/reference/contracts.html:

---

Contracts come in two forms: those constructed by the various operations listed in this section of the manual, and various ordinary Racket values that double as contracts, including...

---

Once again, thanks for the information.

-- Jonathan

[Sam Tobin-Hochstadt]

That error message is generated here:
https://github.com/racket/racket/blob/master/racket/src/cs/rumble/number.ss#L364

It uses the term "contract", and the exception is an instance of
`exn:fail:contract`, but it is not generated by the `racket/contract`
library.

> I take it that the contract error above was generated by a lower-level contract then. I've only glanced at contracts, so I assume this is documented somewhere. Is this section of the Reference referring to the simple contracts that you mention? From https://docs.racket-lang.org/reference/contracts.html:
> ---
> Contracts come in two forms: those constructed by the various operations listed in this section of the manual, and various ordinary Racket values that double as contracts, including...
> ---

That whole section of the reference is about the `racket/contract`
library, and thus the second kind of contracts that I mentioned.

Sam

[Robby Findler]

A little more information about these things.

I'd say that there are two obstacles to having the racket/contract library actually be the source of the contract checks in all functions exported by the racket language/library:

1) dependency layering. The racket/contract library is really a library. So if that library needs something to actually implement the contract system (eg string manipulation libraries, which are handy for constructing error messages), then it can't have a contract that is implemented by the library

2) performance. The contract system has gobs of special cases to get quite close in various situations but it still doesn't quite ever achieve the performance of just writing a simple check at the start of the function (unfortunately). It can be difficult to predict which cases those are (and there are plenty of situations when the raw overhead of the contract checking isn't what matters for the performance) but this is an area I'd like to improve somehow.

One consequence is that some care has been taken, both in the contract system and in functions like number->string, to make the error messages look uniform. A giveaway, however, is the "blaming" line, which the racket/contract contract checking always has and the simple number->string function checks do not. Including that line forces us to give up on the performance benefits of just doing the simple check (since that line requires a precise accounting of who called whom and we have only an approximate accounting of that from a stacktrace unless we add what has been deemed (quite reasonably, IMO) unacceptable overhead).

hth,Robby

--
You received this message because you are subscribed to the Google Groups "Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to racket-users...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/CAK%3DHD%2BYVJbsqvBzT-52meaoj8vV9XkdXXPFC%3DgL1JTCVxNTizA%40mail.gmail.com.

[Jonathan Simpson]

Thanks Sam, Robby. Your explanations make perfect sense. I was conflating contract exceptions with the contract library. I had just assumed they were one and the same. Avoiding the contract library for performance reasons in some cases also seems quite reasonable to me.

Thanks again!

-- Jonathan

[matt...@ccs.neu.edu]

Northeastern has taken down its research machines and network for major repairs.
The outage will last from today June 30 through July 2. We have been reassured
that it will come back then several times. The most observable effect for Racket
Users is the absence of `planet`.

— Matthias

[Sam Tobin-Hochstadt]

Unfortunately, this has had larger impact than we expected, because a
number of places linked directly to mirror.racket-lang.org, which
normally hosts downloads. That machine will be down until July 2. In
particular, this seems to affect the setup-racket GitHub Action and
the homebrew formula for Racket.

The main download site, download.racket-lang.org, still works as
normal, and linking to that site will continue to work.

Sam

> --
> You received this message because you are subscribed to the Google Groups "Racket Users" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to racket-users...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/FFF48AE0-6271-4151-969D-3A825CDC9C6D%40ccs.neu.edu.

[matt...@ccs.neu.edu]

The machines should all be back up and work as usual. If you see any problems, post to this list. — Matthias

[Shu-Hung You]

The PLaneT website (https://planet.racket-lang.org/) is currently
unreachable. The error message is ERR_CONNECTION_REFUSED.

[Robby Findler]

Ah, sorry about this. It should be up now.

Robby

On Fri, Jul 2, 2021 at 11:05 PM Shu-Hung You <shh...@u.northwestern.edu> wrote:

The PLaneT website (https://planet.racket-lang.org/) is currently
unreachable. The error message is ERR_CONNECTION_REFUSED.

--
You received this message because you are subscribed to the Google Groups "Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to racket-users...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/CAMTzy%2Bb9GkCr_rpFnwUUTrB1PCoXsb%2BCBnEv1cbxNtqK2nKF9A%40mail.gmail.com.