Page MenuHomePhabricator

[llvm-libc] Add memory function benchmarks
ClosedPublic

Authored by gchatelet on Jan 10 2020, 8:57 AM.

Details

Summary

This patch adds a benchmarking infrastructure for llvm-libc memory functions.

In a nutshell, the code can benchmark small and large buffers for the memcpy, memset and memcmp functions.
It also produces graphs of size vs latency by running targets of the form render-libc-{memcpy|memset|memcmp}-benchmark-{small|big}.

The configurations are provided as JSON files and the benchmark also produces a JSON file.
This file is then parsed and rendered as a PNG file via the render.py script (make sure to run pip3 install matplotlib scipy numpy).
The script can take several JSON files as input and will superimpose the curves if they are from the same host.

TODO:

  • The code benchmarks whatever is available on the host but should be configured to benchmark the -to be added- llvm-libc memory functions.
  • Produce scores to track the performance of the functions over time to allow for regression detection.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
abrachet added inline comments.Jan 10 2020, 12:13 PM
libc/utils/benchmarks/CMakeLists.txt
185

newline

libc/utils/benchmarks/json.cc
31 ↗(On Diff #237350)

All of these assign to Out but we have ErrorOr<T> which is more ergonomic I think.

149–152 ↗(On Diff #237350)

Was this clang-formats doing?

libc/utils/benchmarks/json_test.cc
119 ↗(On Diff #237350)

EXPECT_THAT is used a lot when other EXPECT_* would probably do. This one is just EXPECT_EQ(Parsed, S), no? I've never really used matchers too much so maybe I'm missing something.

libc/utils/benchmarks/libc_benchmark.cc
18 ↗(On Diff #237350)

Maybe static_assert is fine? But I'm dubious that this is really needed to be honest.

libc/utils/benchmarks/libc_benchmark.h
33–41 ↗(On Diff #237350)
#include "benchmark/benchmark.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/SmallVector.h"
#include <array>
#include <chrono>
#include <cstdint>

Per style guide,. Here and other places too.,

53–55 ↗(On Diff #237350)

Comments should end with .

85–89 ↗(On Diff #237350)

Usually enumerations are not all capitalized.

libc/utils/benchmarks/libc_memory_benchmark.h
149 ↗(On Diff #237350)
172 ↗(On Diff #237350)
libc/utils/benchmarks/libc_memory_benchmark_test.cc
26 ↗(On Diff #237350)

llvm::distance(AB)
This is another example, couldn't this be EXPECT_EQ(..., 0U)?

libc/utils/benchmarks/memcpy.cc
22 ↗(On Diff #237350)

Does this need to be a function pointer and not llvm::function_ref or std::function?

52 ↗(On Diff #237350)

The explicit dereference of a function pointer is not necessary

Just one comment in response to a comment. Will do a detailed review as soon as I can get to it.

libc/utils/HdrGen/CMakeLists.txt
2

Apparently, this is required to build when configured with -DBUILD_SHARED_LIBS=ON. This is being used with other table-gen targets as well. For example: https://github.com/llvm/llvm-project/blob/master/clang/utils/TableGen/CMakeLists.txt

I notice you have a TODO to add a README.md. But, I think some doc like that would really help review this better.

This is a very big patch and I don't have too much time today so I haven't reviewed this all and I focused on llvm style for now. A lot of comments I only made once but apply throughout.

I know something was posted on the mailing list today and I'm guessing this was talked about offline before work started here but I wish this was done more incrementally and discussed on the lists before. This is pretty hard to review as it is.

My apologies for this, we wanted to have the patch and the post ready at the same time so people could refer to each other and get a better idea of the proposal.
It's not too late to split this into multiple patches if you feel like it's worth it.

I notice you have a TODO to add a README.md. But, I think some doc like that would really help review this better.

Yes indeed, I'll work on it right away.

gchatelet updated this revision to Diff 237884.Jan 14 2020, 1:46 AM
  • Split benchmarking targets into render and display
  • Fix missing return value warning
  • Make small configuration run up to 1KiB
  • Change window position in graph
  • Add README with quickstart
gchatelet updated this revision to Diff 237904.Jan 14 2020, 2:53 AM
gchatelet marked 7 inline comments as done.
  • Add missing newline
  • Remove trailing _ in header guard
  • Use quotes for includes
  • Rename cc files to cpp
  • Remove *- C++ -* in cpp files
  • Change filename case
  • Reorder include
  • Fix test error
gchatelet updated this revision to Diff 237941.Jan 14 2020, 5:06 AM
gchatelet marked 19 inline comments as done.
  • Fix JSON comments and tests
  • Fix missing comments trailing dot
  • Fix enum case
  • Moved NDEBUG warning to main
  • Removed unneeded inline keyword
  • Remove function pointer dereferencing
  • Used regular EXPECT wherever possible
libc/utils/benchmarks/json.cc
31 ↗(On Diff #237350)

The JSON framework relies on overloading to dispatch the serialization to the correct function, e.g.

Error fromJson(const json::Value &V, double &Out)
Error fromJson(const json::Value &V, std::string &Out)
Error fromJson(const json::Value &V, uint32_t &Out)
...

C++ can't overload on return value so I can't use ErrorOr<T> here.

123 ↗(On Diff #237350)

for (size_t I = 0, Size = A->size(); I < Size; ++I)

Done

Also there was a thread a while ago considering that we move to ssize_t because apparently loops can be unrolled better with signed integers, do with that whatever you want.

I've heard the opposite argument. Could you point me to that thread?

Also you're doing something with A and Out you can try llvm::zip maybe.

Done thx !

149–152 ↗(On Diff #237350)

Yes what's the problem here?

libc/utils/benchmarks/json_test.cc
119 ↗(On Diff #237350)

In that case no because we have to instruct gtest how the two structs are comparing equals (hence the Equals overrides above).

That said for the other ones yes they're only comparing strings so EXPECT_EQ works.

libc/utils/benchmarks/libc_benchmark.cc
18 ↗(On Diff #237350)

Moved it to LibcMemoryBenchmarkMain.cpp as a static_assert

libc/utils/benchmarks/memcpy.cc
22 ↗(On Diff #237350)

What would be the advantage of using llvm::function_ref or std::function over raw function pointer? I don't want the type to be erased here.

gchatelet updated this revision to Diff 237942.Jan 14 2020, 5:09 AM
  • Remove heading whitespace
gchatelet updated this revision to Diff 237945.Jan 14 2020, 5:10 AM
Rebasing

- Add missing headers
- Split benchmarking targets into render and display
- Fix missing return value warning
- Make small configuration run up to 1KiB
- Change window position in graph
- Add README with quickstart
- Add missing newline
- Remove trailing _ in header guard
- Use quotes for includes
- Rename cc files to cpp
- Remove `*- C++ -*` in cpp files
- Change filename case
- Reorder include
- Fix test error
- Fix JSON comments and tests
- Fix missing comments trailing dot
- Fix enum case
- Moved NDEBUG warning to main
- Removed unneeded inline keyword
- Remove function pointer dereferencing
- Used regular EXPECT wherever possible
- Remove heading whitespace
Harbormaster completed remote builds in B43931: Diff 237945.

I did one detailed pass. I don't claim to understand the code fully but in general I do not see anything popping out as a big problem. I left a few inline comments, but an overall comment is that there are style violations at many places. @abrachet pointed out few of them, but I see there are a number of others as well. Especially, the variable naming convention follows google-style and not LLVM-style.

libc/utils/benchmarks/CMakeLists.txt
57

Would just add_unittest work? If it does, it should be used here.

93

You don't need to do it separately like this. You can specify SUITE option when listing the add_libc_unittest target.

libc/utils/benchmarks/Memcmp.cpp
35

::memcpy ?

libc/utils/benchmarks/README.md
2

Limit to 80 char lines.

86

RATIONALE.md is missing?

libc/utils/benchmarks/libc_benchmark.cc
24 ↗(On Diff #237350)

Can we provide instructions on how to disable CPU scaling? Better, can we provide a script with which one can disable CPU scaling and then restore if they want to?

We don't have to do it with this change, but we should eventually do it. I had to play around a bit to disable CPU scaling.

gchatelet updated this revision to Diff 238462.Jan 16 2020, 4:51 AM
gchatelet marked 5 inline comments as done.
  • Add missing headers
  • Split benchmarking targets into render and display
  • Fix missing return value warning
  • Make small configuration run up to 1KiB
  • Change window position in graph
  • Add README with quickstart
  • Add missing newline
  • Remove trailing _ in header guard
  • Use quotes for includes
  • Rename cc files to cpp
  • Remove *- C++ -* in cpp files
  • Change filename case
  • Reorder include
  • Fix test error
  • Fix JSON comments and tests
  • Fix missing comments trailing dot
  • Fix enum case
  • Moved NDEBUG warning to main
  • Removed unneeded inline keyword
  • Remove function pointer dereferencing
  • Used regular EXPECT wherever possible
  • Remove heading whitespace
  • Format README.md to respect 80 columns
  • Use SUITE instead of custom test target
  • anchor memcpy
libc/utils/benchmarks/CMakeLists.txt
57

I couldn't make it work. We can try to change it afterwards though.

gchatelet updated this revision to Diff 238463.Jan 16 2020, 5:03 AM
  • Fix variable case

I did one detailed pass. I don't claim to understand the code fully but in general I do not see anything popping out as a big problem. I left a few inline comments, but an overall comment is that there are style violations at many places. @abrachet pointed out few of them, but I see there are a number of others as well. Especially, the variable naming convention follows google-style and not LLVM-style.

I believe I fixed all of the variables. Do you see any other ones?

This change is fine with me. I will let @ckennelly approve it. A nit inline, and also, is RATIONALE.md still missing?

libc/utils/benchmarks/render.py
8 ↗(On Diff #238463)

The instructions here and in README.md imply that the script is Python3 only. I tried with Python 2 and it seems to work. More important though:

  1. If you want it to be Python 3 only, probably say it here and in README.md.
  2. The CMake rule which runs this script runs python and not python3. Again, if you want this script to be Python 3 only going forward, then use python3 in the CMake rule as well.

This change is fine with me. I will let @ckennelly approve it. A nit inline, and also, is RATIONALE.md still missing?

Yes it's missing, I'm still working on it : )
I'll add it today.

gchatelet updated this revision to Diff 238714.Jan 17 2020, 1:22 AM
gchatelet marked 2 inline comments as done.
  • Be explicit about Python3 usage
libc/utils/benchmarks/render.py
8 ↗(On Diff #238463)

Python2 is officially deprecated so it has to be Python3 :)

I've changed the file extension and updated the README.md file.

gchatelet updated this revision to Diff 238724.Jan 17 2020, 2:42 AM
  • Add instructions for frequency scaling
  • Add RATIONALE.md file
gchatelet updated this revision to Diff 239043.Mon, Jan 20, 2:40 AM
  • Rebase and fix broken unit tests
gchatelet edited the summary of this revision. (Show Details)Mon, Jan 20, 2:40 AM
sivachandra added inline comments.Wed, Jan 22, 8:30 AM
libc/cmake/modules/LLVMLibCRules.cmake
320 ↗(On Diff #239043)

Do we still need the changes in this file?

ckennelly requested changes to this revision.Wed, Jan 22, 2:29 PM
ckennelly added inline comments.
libc/utils/benchmarks/Memcmp.cpp
65

Should we setup an analogous benchmark for bcmp?

This revision now requires changes to proceed.Wed, Jan 22, 2:29 PM
sivachandra added inline comments.Wed, Jan 22, 2:36 PM
libc/utils/benchmarks/Memcmp.cpp
65

Shoud llvm-libc provide bcmp at all?

abrachet added inline comments.Wed, Jan 22, 2:49 PM
libc/utils/benchmarks/Memcmp.cpp
65

In what I believe was @gchatelet's email on the list said they were hoping !memcmp(...) would be emitted as !bcmp(...) for efficiency. clang does make this optimization.

MaskRay added inline comments.Wed, Jan 22, 2:58 PM
libc/utils/benchmarks/Memcmp.cpp
65

TargetLibraryInfo.cpp

static bool hasBcmp(const Triple &TT) {
  // Posix removed support from bcmp() in 2001, but the glibc and several
  // implementations of the libc still have it.
  if (TT.isOSLinux())
    return TT.isGNUEnvironment() || TT.isMusl();
  // Both NetBSD and OpenBSD are planning to remove the function. Windows does
  // not have it.
  return TT.isOSFreeBSD() || TT.isOSSolaris();
}

On certain platforms (including Linux), memcmp can be optimized to bcmp if preferable.

sivachandra added inline comments.Wed, Jan 22, 3:15 PM
libc/utils/benchmarks/Memcmp.cpp
65

To be honest, I do not have any opinion. If others more knowledgeable in this area decide llvm-libc should have a bcmp, then we will go with it.

Just pointing out though: musl's bcmp just calls into memcmp, and in glibc, bcmp is an alias of memcmp.

MaskRay added inline comments.Wed, Jan 22, 3:38 PM
libc/utils/benchmarks/Memcmp.cpp
65

POSIX.1-2001 marked bcmp obsoleted and POSIX.1-2008 deleted bcmp, but in reality, bcmp has performance benefits (the 3-state -> 2-state transformation allows unordered comparison).

Eventually we should have bcmp. Before it is optimized, you may make it an alias of memcmp.

sivachandra added inline comments.Wed, Jan 22, 4:18 PM
libc/utils/benchmarks/Memcmp.cpp
65

To be clear: I understand why bcmp is/can be faster when doing a plain equality check. My point is specifically about why a libc should provide it, especially when it is being removed from the standards. And, as I said, if libc happens to be the best place for bcmp, then so be it. May be alternates like compiler intrinsics have been considered (I will be surprised if not.) So, when adding bcmp, we should ideally also add justification for why a libc is the right place.

gchatelet updated this revision to Diff 239918.Thu, Jan 23, 8:49 AM
gchatelet marked an inline comment as done.
  • Add bcmp comment

@ckennelly looks good to you?

libc/utils/benchmarks/Memcmp.cpp
65

Yes indeed we already have an optimization in clang to convert (bool)memcmp to bcmp, this is the second bullet in the LLVM 9.0.0 release notes.

Since the current code is benchmarking the host's libc and not llvm-libc (yet) I will just provide a comment to make sure we benchmark bcmp once it is known to be available.

sivachandra added inline comments.Thu, Jan 23, 9:04 AM
libc/cmake/modules/LLVMLibCRules.cmake
320 ↗(On Diff #239043)

Pointing out again: The changes in this file are OK, but if they are not required for the rest of the change, they should probably be done separately.

ckennelly accepted this revision.Thu, Jan 23, 9:08 AM
This revision is now accepted and ready to land.Thu, Jan 23, 9:08 AM
gchatelet updated this revision to Diff 240131.Fri, Jan 24, 2:23 AM
gchatelet marked 11 inline comments as done.
  • Revert LLVMLibCRules.cmake
gchatelet added inline comments.Fri, Jan 24, 2:24 AM
libc/cmake/modules/LLVMLibCRules.cmake
320 ↗(On Diff #239043)

Thx for your comment. I'm reverting this file but note that compiling llvm-libc with shared libraries still fails because of a missing LINK_COMPONENTS Support in libc/utils/UnitTest/CMakeLists.txt

This revision was automatically updated to reflect the committed changes.