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

[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

On Tuesday, June 29, 2021 at 12:45:15 PM UTC-4 Robby Findler wrote:

> 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
>
>
> On Tue, Jun 29, 2021 at 11:11 AM Sam Tobin-Hochstadt  
> wrote:
>
>> On Tue, Jun 29, 2021 at 12:04 PM Jonathan Simpson  
>> wrote:
>> >
>> > On Monday, June 28, 2021 at 10:25:36 PM UTC-4 Sam Tobin-Hochstadt wrote:
>> >>
>> >> On Mon, Jun 28, 2021 at 9:46 PM Jonathan Simpson wrote:
>> >> >
>> >> > 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?
>> >>
>> >> 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
>> >
>> >
>> > 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"
>> > ---
>>
>> 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 

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

[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


On Tue, Jun 29, 2021 at 11:11 AM Sam Tobin-Hochstadt 
wrote:

> On Tue, Jun 29, 2021 at 12:04 PM Jonathan Simpson 
> wrote:
> >
> > On Monday, June 28, 2021 at 10:25:36 PM UTC-4 Sam Tobin-Hochstadt wrote:
> >>
> >> On Mon, Jun 28, 2021 at 9:46 PM Jonathan Simpson wrote:
> >> >
> >> > 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?
> >>
> >> 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
> >
> >
> > 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"
> > ---
>
> 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
>
> --
> You 

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

[Sam Tobin-Hochstadt]

On Tue, Jun 29, 2021 at 12:04 PM Jonathan Simpson  wrote:
>
> On Monday, June 28, 2021 at 10:25:36 PM UTC-4 Sam Tobin-Hochstadt wrote:
>>
>> On Mon, Jun 28, 2021 at 9:46 PM Jonathan Simpson wrote:
>> >
>> > 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?
>>
>> 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
>
>
> 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"
> ---

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

-- 
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/CAK%3DHD%2BYVJbsqvBzT-52meaoj8vV9XkdXXPFC%3DgL1JTCVxNTizA%40mail.gmail.com.

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

[Jonathan Simpson]

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

> On Mon, Jun 28, 2021 at 9:46 PM Jonathan Simpson wrote: 
> > 
> > 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? 
>
> 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


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

-- 
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/34b87a4d-5ab3-4c83-9676-e7e560641391n%40googlegroups.com.

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

[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

-- 
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/08b4bcb1-145f-0824-55c0-05bf6641bf06%40sschwarzer.net.

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

[Sam Tobin-Hochstadt]

On Mon, Jun 28, 2021 at 9:46 PM Jonathan Simpson  wrote:
>
> 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?

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

-- 
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/CAK%3DHD%2BZHoN--2uJRVeT%2BMHEtbgcDHWtNMYSD45MKNuutwutrUA%40mail.gmail.com.

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

[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

-- 
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/5e10f23a-7895-42d9-b475-802e08d0ee56n%40googlegroups.com.

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

[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


On Mon, Jun 28, 2021 at 2:18 PM Alessandro Motta  wrote:

> On 27.06.21 19:34, Robby Findler wrote:
> > 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).
>
> 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
>

-- 
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/CAL3TdOMpMpfY4CW8y%2BUZHJFm3Wyv0yYdDhFSvXEfSg6zaDFKNA%40mail.gmail.com.

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

[Alessandro Motta]

On 27.06.21 19:34, Robby Findler wrote:
> 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).

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

-- 
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/cec30f7f-3166-ce1f-9660-9f305f8cdbd5%40gmail.com.

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

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

-- 
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/m2k0mecvqc.fsf%40defn.io.

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.