Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add computation expression over StringBuilder to FSharp.Core #775

Open
aklefdal opened this issue Jul 29, 2019 · 18 comments

Comments

@aklefdal
Copy link

commented Jul 29, 2019

StringBuilder computation expression

I propose we add a computation expression over StringBuilder to FSharp.Core.

Vasily Kirichenko has already created an example implementation, with a demonstration here.

Don Syme mentioned that we will need to add state machine support, although I am not sure about the impact this will have on the implementation difficulty.

Pros and Cons

The advantages of making this adjustment to F# are an easier way of using StringBuilder to create strings, in a way that is idiomatic to F# developers, in the same way sequence expressions are.

The disadvantages of making this adjustment to F# are as I can see none, except the added cost of maintaining an extra feature in the code base.

Extra information

Estimated cost (XS, S, M, L, XL, XXL): S (??? Could be much more with state machine support)

Related suggestions: N/A

Affidavit (please submit!)

Please tick this by placing a cross in the box:

  • This is not a question (e.g. like one you might ask on stackoverflow) and I have searched stackoverflow for discussions of this issue
  • I have searched both open and closed suggestions on this site and believe this is not a duplicate
  • This is not something which has obviously "already been decided" in previous versions of F#. If you're questioning a fundamental design decision that has obviously already been taken (e.g. "Make F# untyped") then please don't submit it.

Please tick all that apply:

  • This is not a breaking change to the F# language design
  • I or my company would be willing to help implement and/or test this

@aklefdal aklefdal changed the title Add 'stringBuffer' computation expression to FSharp.Core Add computation expression over StringBuilder to FSharp.Core Jul 29, 2019

@dsyme

This comment has been minimized.

Copy link
Collaborator

commented Jul 29, 2019

We could also consider

lines { ... }

though there is the question of line endings.

For stringBuffer { ... } we could in theory consider string { ... } as the name to use though it would require a compiler hack as string lready exists in the F# standard library

@wallymathieu

This comment has been minimized.

Copy link

commented Jul 30, 2019

It's an interesting suggestion. I could imagine that you could perhaps do some templating with the help of a few custom verbs.

@wallymathieu

This comment has been minimized.

Copy link

commented Jul 30, 2019

I'd imagine that it could be nice together with something like #262

@gerardtoconnor

This comment has been minimized.

Copy link

commented Aug 3, 2019

Just as some friendly feedback on both the proposal and proto-type snippet

StringBuilder is almost exculsively used to mitigate perfomance concerns around string allocation so if this is to be of benefit from a Stringbuilder perspective, not just a string concat library, that needs to be considered in the design.

In current form I see two possible issues from an allocation perspective,

  • a) string builder is a reusable concatination buffer but we create and disgard after each expression

  • b) the CE, due to SB -> unit Stringbuffer sig is likely going to capture allocate on many of the operations (although this can be tested and mitigated to optimise most of them out)

As a side note, in the example sprintf is being used to create a string that is then added to SB which loses half the builder benefit so some passthough mechanism to utilize "AppendFormat" should be included to avoid intermedite format allocations.

To simplify the question around naming & allow re-use of an existing Stringbuilder, it may be a candidate for extension Builder operations on the SB itself? The final Run op can reset the builder too to make it a clean operation.

example:

let sb = StringBuilder()

let stringBuiltWithStringBuilder1 = sb { // << CE on the StringBuilder instance
    yield "Test "
    yield "Case "
    yield "No1"
} // CE Run op gets string then resets StringBuilder (maintaining buffer etc)

let stringBuiltWithStringBuilder2 = sb { // re-using the SB & Buffer
    yield "Test "
    yield "Case "
    yield "No2"
}

If reusing the same instance is a mental burden/messy for some, we could instead have the CE automatically grab a cached buffer from a thread static cache each time it is needed, as the CE writes, returns and resets all in the one syncronous operation having one cached (but initialised on initial demand) per thread should be perfectly safe.

@wallymathieu

This comment has been minimized.

Copy link

commented Aug 3, 2019

How does that compare to seq { ... } @gerardtoconnor ?

@gerardtoconnor

This comment has been minimized.

Copy link

commented Aug 3, 2019

@wallymathieu its nothing like seq { … } , seq is quite special in that it can be used like IEnumerable interface but also in FSharp code, be inline application / dispatching of work such that a yield is running the body of code inline each time (a code execution data structure) .... this SB CE is a far simpler concept of folding string inputs into the buffer, but ensuing clean-up/reset at the end.

I just know myself that StringBuilders can and should be re-used so this should be factored into the design

@wallymathieu

This comment has been minimized.

Copy link

commented Aug 3, 2019

Good to know. I didn't know these things around StringBuilders, but I guess it makes sense since it looks sort of like Memory<char>.

@gerardtoconnor

This comment has been minimized.

Copy link

commented Aug 3, 2019

Like List in System.Collections.Generic, the nice thing is you can add to the collection without worrying about overflow, both automatically grow the internal buffer array and manage that, and importantly, you can reset/clear both and reuse the existing buffer. Memory is an allocating (vs Span) array-like windowed slice over an array buffer so its a more generalised interface for buffer interactions.

@cartermp

This comment has been minimized.

Copy link
Member

commented Aug 3, 2019

Not perfect but here's what it looks like for 10k random strings up to 25 chars in length: https://gist.github.com/cartermp/e32b34fe62fe026ff3c4e5121b51aaad

BenchmarkDotNet=v0.11.5, OS=macOS Mojave 10.14.5 (18F132) [Darwin 18.6.0]
Intel Core i7-7700HQ CPU 2.80GHz (Kaby Lake), 1 CPU, 8 logical and 4 physical cores
.NET Core SDK=3.0.100-preview5-011568
  [Host]     : .NET Core 3.0.0-preview5-27626-15 (CoreCLR 4.6.27622.75, CoreFX 4.700.19.22408), 64bit RyuJIT DEBUG
  DefaultJob : .NET Core 3.0.0-preview5-27626-15 (CoreCLR 4.6.27622.75, CoreFX 4.700.19.22408), 64bit RyuJIT

Method Mean Error StdDev Ratio Gen 0 Gen 1 Gen 2 Allocated
Concats 168.363 ms 7.1132 ms 20.5233 ms 1.00 501000.0000 313333.3333 312666.6667 1104.47 MB
StringBuilder 4.538 ms 0.0903 ms 0.2215 ms 0.03 1523.4375 359.3750 31.2500 2.89 MB
CompExpr 4.418 ms 0.0530 ms 0.0470 ms 0.03 1593.7500 312.5000 70.3125 3.35 MB
@gerardtoconnor

This comment has been minimized.

Copy link

commented Aug 3, 2019

@cartermp thanks for testing ... but the fact that the CE is faster then the vanilla Stringbuilder seems wrong/unlikely and testing anomaly. I think the vast majority of your test time is building the random strings, rather than the concat/building. It may be more conclusive if you pre-build the random strings into an array and then have them all work off that array?

@slang25

This comment has been minimized.

Copy link

commented Aug 4, 2019

Here are the results for a pre-allocated array:

BenchmarkDotNet=v0.11.5, OS=macOS Mojave 10.14.6 (18G87) [Darwin 18.7.0]
Intel Core i7-8750H CPU 2.20GHz (Coffee Lake), 1 CPU, 12 logical and 6 physical cores
.NET Core SDK=2.2.300
  [Host]     : .NET Core 2.2.5 (CoreCLR 4.6.27617.05, CoreFX 4.6.27618.01), 64bit RyuJIT DEBUG
  DefaultJob : .NET Core 2.2.5 (CoreCLR 4.6.27617.05, CoreFX 4.6.27618.01), 64bit RyuJIT
Method Mean Error StdDev Ratio Gen 0 Gen 1 Gen 2 Allocated
Concats 161,188.4 us 3,506.2777 us 8,056.2561 us 1.000 338000.0000 308000.0000 308000.0000 1114479.45 KB
StringBuilder 142.7 us 0.7851 us 0.6556 us 0.001 51.2695 8.5449 - 236.44 KB
CompExpr 466.3 us 4.8994 us 4.0912 us 0.003 142.5781 71.2891 71.2891 703.02 KB

https://gist.github.com/slang25/ea89d25d3905f0047c9cf7b35b0bd99a

@cartermp

This comment has been minimized.

Copy link
Member

commented Aug 4, 2019

@gerardtoconnor I think either scenario is valid, since it's also common to generate something and append/add/etc. to a buffer of some sort. I think in either case (generate on the fly, or run through an existing buffer) it's clear that allocations and CPU time are proportional to using the .NET API directly. So I don't think that gating this on something like state machine support would be a requirement.

@gerardtoconnor

This comment has been minimized.

Copy link

commented Aug 4, 2019

@cartermp I respectfully do not find it useful and insightful for performance optimisation to have common code that is performance volatile (as Random is) and consumes 90% of the CPU time, if I can easily strip it out and get a clean more isolated execution path of the code in question ... @slang25 test results show the more expected results that the vanilla usage is 3x faster while the random generation in your results contradict this with the CE being faster due to the volatility on the random generation accounting for circa 90% CPU, and the actual code in question being about 10%, The high Error and StDev numbers confirm this with random gen inline being nearly 1000x more volatile.

I am just giving some performance design feedback and feel; if we can; a BCL implementation should be as performant as possible without compromising simplicity and correctness. If a thread uses a SB more then a few times in apps runtime, it should re-use the same buffer, it's quite simple to do this with either way I've described, 1) SB instance as Builder, or 2) ThreadStatic Singleton Cache

Appreciate you don't want to complicate things as that can inevitably slow development but compared to the task state machine proposal, this is relatively simple and already 80/90% there thanks to the provided example.

I guess a more pressing question is what variable name to give the CE, str { ... } , concat { ... } are other options?, and how do we utilise the format api (.AppendFormat) so that we eliminate intermediate format strings from sprintf etc.

@cartermp

This comment has been minimized.

Copy link
Member

commented Aug 4, 2019

I respectfully do not find it useful and insightful for performance optimisation to have common code that is performance volatile (as Random is) and consumes 90% of the CPU time, if I can easily strip it out and get a clean more isolated execution path of the code in question

This is why it's a statistical benchmark and generating 10k of these things per run 🙂. Given that each run has a similar error and standard deviation, it's probably fine. Real world usage of APIs doesn't act on uniform data either.

the more expected results that the vanilla usage is 3x faster while the random generation in your results contradict this with the CE being faster due to the volatility on the random generation accounting for circa 90% CPU

I think this is missing the forest for the trees here. 3x faster . . . on a scale where both are 2 orders of magnitude faster in CPU time and allocate orders of magnitude less memory.

this is relatively simple and already 80/90% there thanks to the provided example.

More like 97%, if either benchmark is to be taken seriously. Which is why I'm suggesting that inclusion not be gated on state machine generation.

@slang25

This comment has been minimized.

@cartermp

This comment has been minimized.

Copy link
Member

commented Aug 4, 2019

TBH I think I prefer stringBuffer to sb or stringBuilder and so on. But stringBuilder does make it obvious what this is, and the name matches loads of existing documentation and other web stuff giving a clear indicator of what it does.

@gerardtoconnor

This comment has been minimized.

Copy link

commented Aug 4, 2019

@slang25 Yes, I was thinking something along those lines but as @cartermp points out, we're already 97% there so probably over engineering it as most will not care on the materiality of the intermediate string alloc.

Out of interest, I tested the reusable buffer and its bit faster but due to CE for expression forcing the array to an IEnumerable, it's difficult to compete with raw loop sb example is using

BenchmarkDotNet=v0.11.5, OS=Windows 10.0.18362
Intel Core i7-8550U CPU 1.80GHz (Kaby Lake R), 1 CPU, 8 logical and 4 physical cores
.NET Core SDK=3.0.100-preview7-012821
  [Host]     : .NET Core 3.0.0-preview7-27912-14 (CoreCLR 4.700.19.32702, CoreFX 4.700.19.36209), 64bit RyuJIT DEBUG
  DefaultJob : .NET Core 3.0.0-preview7-27912-14 (CoreCLR 4.700.19.32702, CoreFX 4.700.19.36209), 64bit RyuJIT
Method Mean ErrorStdDevRatioGen 0Gen 1Gen 2Allocated
Concats147,078.4 us2,712.482 us2,664.020 us1.000345333.3333315333.3333311333.33331124687.66 KB
StringBuilder146.5 us1.262 us1.119 us0.00157.373019.0430-236.44 KB
CompExpr449.2 us3.603 us3.194 us0.003142.578171.289171.2891702.46 KB
SBCE302.8 us4.517 us4.225 us0.00271.289171.289171.2891231.44 KB
@ChrisPritchard

This comment has been minimized.

Copy link

commented Aug 14, 2019

Is all this really necessary? Hopefully this doesn't come off as too negative, but F# is a hybrid language and we should be hybrid developers: just use StringBuilder if you need it. Its right there, and it doesn't bite :)

Sure its a bit painful with its .NET 1.1 flavour, but I am not sure a computation expression for composing strings is much of an improvement.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
7 participants
You can’t perform that action at this time.