[SR-8908] Add insert(_:Character) benchmarks in RangeReplaceableCollection

[swift-ci]

Previous ID	SR-8908
Radar	None
Original Reporter	BalestraPatrick (JIRA User)
Type	Improvement
Status	Resolved
Resolution	Done

Additional Detail from JIRA

Votes	1
Component/s	Standard Library
Labels	Improvement, Benchmark, StarterBug
Assignee	BalestraPatrick (JIRA)
Priority	Medium

md5: f3a7e233341d0f38dd4f1f9f16ad8ea0

Issue Description:

As described in the task SR-8905, I would like to give a try at filling the gap in the benchmarking suite of String RangeReplaceableCollection operations. More specifically, I will add tests for the insert(_:Character) method.

[stephentyrone]

Excellent!

[milseman]

Let me know if you need any help! benchmark/single-source/RemoveWhere.swift has some examples for remove(). There's some work required to register the benchmarks with the benchmark-driver, and you can find an example by grepping for "RemoveWhere" and just follow that pattern.

[milseman]

I found this lying around, in case it helps. As @palimondo said, you may need to add a multiplier to `scale` here to get the right execution time.

@inline(never)
func run_StringRRC_InsertCharacterTowardsEnd(_ scale: Int) {
  var workload = str
  let c = character
  workload.append("!")
  var idx = workload.endIndex
  for i in 0..<scale {
    workload.insert(c, at: idx)
    if i % 1_000 == 0 {
      idx = workload.endIndex
    }
  }
  blackHole(workload)
  CheckResults(workload.count == str.count + 1 + scale)
}

[swift-ci]

Comment by Patrick Balestra (JIRA)

@milseman I was able to add a new file with the example test you have provided and it runs successfully when using the build script. I am now trying to use the `Benchmark_Driver` to run a single test that is inside `swift/benchmark/scripts`. I am running it in this way from the `scripts` folder: `./Benchmark_Driver run 5` and the script is exiting with:

 Traceback (most recent call last):
File "./Benchmark_Driver", line 654, in <module>
exit(main())
File "./Benchmark_Driver", line 650, in main
return args.func(args)
File "./Benchmark_Driver", line 225, in run_benchmarks
driver = BenchmarkDriver(args)
File "./Benchmark_Driver", line 58, in _init_
self.tests = tests or self._get_tests()
File "./Benchmark_Driver", line 111, in _get_tests
self._invoke(self._cmd_list_benchmarks).split('\n')[1:-1]
File "./Benchmark_Driver", line 67, in _invoke
cmd, stderr=self._subprocess.STDOUT)
File "/System/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/subprocess.py", line 566, in check_output
process = Popen(stdout=PIPE, *popenargs, **kwargs)
File "/System/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/subprocess.py", line 710, in _init_
errread, errwrite)
File "/System/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/subprocess.py", line 1335, in _execute_child
raise child_exception
OSError: [Errno 2] No such file or directory

Is there anything that I am missing (like a specific directory from where to run it)?

I am also wondering by reading your other comment if I should try to keep each test run time between 1-10ms when passed `1` as `scale` argument?

Do you maybe have any documentation on what the purpose of `blackHole` and `CheckResults` is? Especially `blackHole` which isn't that self-explanatory 🙂

[milseman]

I run the benchmarks from the build directory like:

[swift/build/Ninja-RelWithDebInfo/swift-macosx-x86_64] $ ./bin/Benchmark_O RemoveWhereQuadraticStrings 

`swift/build/Ninja-Release/swift-macosx-x86_64` is also fine, depending on your build. This is the difference between `build-script -r --no-assertions` and `build-script -R --noassertions`. We want a release no-assertions build of the standard library, as that's what we benchmark. The presence of debug-info usually doesn't affect results.

The output is the per-invocation time in micro-seconds, so it's good to try and target around 1,000 micro-seconds (1 millisecond). CC @palimondo to confirm.

When writing synthetic benchmarks, one issue that comes up frequently is how best to "fake" the operation we're trying to measure, e.g. looping from 1 to N performing the exact same operation. Sometimes the optimizer is smart enough to eliminate the operation or even the entire loop around it. `blackHole` is a public non-inlinable function from another module, and thus is a barrier to the optimizer: the function call must always happen and the program must produce the value which is passed into it.

`CheckResults` is a way of doing a quick correctness check while benchmarking.

[swift-ci]

Comment by Patrick Balestra (JIRA)

@milseman Thanks for the tips! Is there a faster way to recompile the benchmarks only for a faster feedback loop? So far I was able to write three benchmarks: `run_InsertCharacterEndIndex` (which inserts a Character always at endIndex), `run_InsertCharacterStartIndex` (same as before but always startIndex), `run_InsertCharacterMidIndex` (same but always at string.count / 2). I could also add a benchmark for random insertion in various positions? Is there anything else that you think would be needed?

[milseman]

Insert at end could be useful, but it's just modeling append (which we benchmark pretty heavily). Unless it happens to the slower than append, in which case this is a really good thing to detect! Insert at start has the issue of making the benchmark quadratic, as each subsequent loop iteration has to shift more code units down than the one prior. That's why the example I posted does it at various points, but periodically re-shits to closer to the end.

As far as being more productive. I always extract into a single executable source file and develop there before integrating. This doesn't perfectly mimic the benchmark set-up, but it gets close enough for development. You'll still want to test it integrated into the suite. Here's an example where I extracted from single-source/Substring.swift: https://gist.github.com/milseman/9b579ab001f12676b15b40b1b87e9143

[swift-ci]

Comment by Patrick Balestra (JIRA)

@milseman Maybe it's a dumb question, why is it a problem if the benchmark is quadratic? As long as the benchmark is the same, we can always compare it to previous results and make sure that the algorithm doesn't get worse.

Based on your suggestions, I have written InsertCharacterEndIndex and InsertCharacterTowardsEndIndex with ASCII strings. Would it be useful to have the same tests with non-ASCII characters?

[milseman]

It depends on how you write the loop. We'd want performance to scale linearly with the function parameter (`N` in the example code), so that the benchmark driver can estimate what value to feed in. You can have two nested loops in that case, where the outer one is from `0..<N` is linear in time, resets the string, and the inner loop is the quadratic one.

We definitely want non-ASCII workloads as well. Try inserting a complex emoji such as https://emojipedia.org/female-teacher-type-4/, which is comprised of 4 unicode scalars, three of which are not on the BMP.

[swift-ci]

Comment by Patrick Balestra (JIRA)

Fixed in #19941

[palimondo]

Sorry for not responding sooner. This turned out as a nice benchmark family, good job Patrik!

As for your question about productivity when working with Swift Benchmarking Suite, after the initial build (form swift-source directory) with ./swift/utils/build-script -R -B you can use ninja -C ${SWIFT_BUILD_DIR} swift-benchmark-macosx-x86_64 which can be faster. SWIFT_BUILD_DIR is in my case: /Users/mondo/Developer/swift-source/build/Ninja-ReleaseAssert/swift-macosx-x86_64. In my experience, this incremental build takes about 1 minute on my ancient machine. But once you commit anything, the whole swift library would be rebuilt, because of the changed "version" (derived from commit). That takes 1 hour on my machine.

For running individual benchmarks, go to the build binaries:
$ cd ${SWIFT_BUILD_DIR}/bin/
And get to know how to use the driver binary (there are 3 variants with different optimizations: O, Osize and Onone):
$ ./Benchmark_O --help
$ ./Benchmark_O ArrayLiteral -``-num-samples=1 --quantile=4 --memory
— add --verbose flag to see all the nitty-gritty under the hood

There's also a higher level python wrapper that takes care of repeated measurements and supports regex filters for selecting what to measure, which comes in handy when you work on a family of benchmarks.
$ ./Benchmark_Driver --help
$ ./Benchmark_Driver run --help
$ ./Benchmark_Driver run -f InsertCharacter -i 5
— this will take 5 independent samples (i.e. running Benchmark_O five times and combining the measurements into single summary statistics) from all benchmarks that starts with "InsertCharacter"

For new benchmarks it is important to run check, that verifies that they conform to all the best practices:
$ ./Benchmark_Driver check -``f InsertCharacter
— you can add --verbose for more details

(JIRA's text formatting is the WORST!)