Re: [racket-users] Speeding up the conversion of flvectors to string

[Bogdan Popa]

Matthew Flatt writes:

> At Sun, 27 Jun 2021 21:36:09 +0300, Bogdan Popa wrote:
> 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.

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

-- 
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/racket-users/m2mtrbcbpg.fsf%40defn.io.

Re: [racket-users] Speeding up the conversion of flvectors to string

[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.

-- 
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/racket-users/20210627135005.2f6%40sirmail.smtps.cs.utah.edu.

Re: [racket-users] Speeding up the conversion of flvectors to string

[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.

On Sunday, June 27, 2021 at 11:36:14 AM UTC-7 bogdan 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:
>
> #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 500))
> (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 10)]
> [y (make-flvector 10)])
> (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.
>
>
> Jens Axel Søgaard writes:
>
> > 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
>

-- 
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+unsubscr...@googlegroups.com.
To 

Re: [racket-users] Speeding up the conversion of flvectors to string

[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 500))
(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 10)]
   [y (make-flvector 10)])
   (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.


Jens Axel Søgaard writes:

> Den søn. 27. jun. 2021 kl. 18.58 skrev Alessandro Motta >:
>
>> 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

-- 
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/racket-users/m2pmw7cfza.fsf%40defn.io.

Re: [racket-users] Speeding up the conversion of flvectors to string

[Jens Axel Søgaard]

Den søn. 27. jun. 2021 kl. 18.58 skrev Alessandro Motta :

> 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

-- 
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/racket-users/CABefVgzku_POA_673-bChPe1jyij_yQ9dH0Yuu6fR-VMAghwGg%40mail.gmail.com.

Re: [racket-users] Speeding up the conversion of flvectors to string

[Robby Findler]

On Sun, Jun 27, 2021 at 11:58 AM Alessandro Motta 
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

-- 
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/racket-users/CAL3TdOOkJjkH7Qoayjm%2BVhZ6aK9_vnDOZ_1cvFJ_RSxZJRTDNA%40mail.gmail.com.

Re: [racket-users] Speeding up the conversion of flvectors to string

[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

On 27.06.21 16:29, 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.
> 
> 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
> 
> 
> On Sun, Jun 27, 2021 at 9:10 AM Bogdan Popa  > wrote:
> 
> 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 10)]
>            [y (make-flvector 10)])
>        (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
> 
> Alessandro Motta writes:
> 
> > 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
> 
> >
> 

Re: [racket-users] Speeding up the conversion of flvectors to string

[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


On Sun, Jun 27, 2021 at 9:10 AM Bogdan Popa  wrote:

> 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 10)]
>[y (make-flvector 10)])
>(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
>
> Alessandro Motta writes:
>
> > 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
>
> --
> 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+unsubscr...@googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/racket-users/m2v95zcs9v.fsf%40defn.io.
>

-- 
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/racket-users/CAL3TdOM7YZ8P3E7WUH6fg4FF%2BgsXupbCYy8apNtbF97itFg1fw%40mail.gmail.com.

Re: [racket-users] Speeding up the conversion of flvectors to string

[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


Bogdan Popa writes:

> 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 10)]
>[y (make-flvector 10)])
>(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
>
> Alessandro Motta writes:
>
>> 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

-- 
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/racket-users/m2sg13crgy.fsf%40defn.io.

Re: [racket-users] Speeding up the conversion of flvectors to string

[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) " "))


Den søn. 27. jun. 2021 kl. 15.26 skrev 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
>
> --
> 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+unsubscr...@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

-- 
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/racket-users/CABefVgwV%3DZ9We2ZHAFBP1yUdbpkSVP76LBBuU3%2Bdkysm4WYH_Q%40mail.gmail.com.

Re: [racket-users] Speeding up the conversion of flvectors to string

[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 10)]
   [y (make-flvector 10)])
   (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

Alessandro Motta writes:

> 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

-- 
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/racket-users/m2v95zcs9v.fsf%40defn.io.

[racket-users] 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

-- 
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+unsubscr...@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.