This is an archive of the discontinued LLVM Phabricator instance.

[libc++][format] Buffer changes proof-of-concept
AbandonedPublic

Authored by Mordante on Oct 23 2021, 4:41 AM.

Details

Reviewers
None
Group Reviewers
Restricted Project
Summary

In D110495 @vitaut suggested a different approach for the buffers. This is
a proof-of-concept of that idea.

  • There's a new __output_buffer that contains the fixed size buffer. The __iterator_wrapper_buffer now always call the put of this buffer. When the buffer is full the buffer calls flush of one of the original buffers.
  • The original buffers are still called buffer, but they're no longer buffers; they are more a write policy. This needs to be renamed once backported.
  • All format functions call __output_buffer:;flush(). It would be possible to do that with an RAII buffer, but since flush then throw from the destructor some guards were needed. This slowed the performance.
  • There are before and after benchmark timings using D110501 Before -> D110500 After -> This patch. In general this approach seems to be an improvement. The notable exception is when using std::list::begin() as iterator. This hasn't been investigated, since I don't expect this to be used in real applications.
  • This patch is just for discussion, the code is not ready for review and should be folded back in the earlier patches in this series. Especially the two objects called buffer should be changed.

Depends on D110500

Diff Detail

Event Timeline

Mordante requested review of this revision.Oct 23 2021, 4:41 AM
Mordante created this revision.
Herald added a project: Restricted Project. · View Herald TranscriptOct 23 2021, 4:41 AM
Herald added a reviewer: Restricted Project. · View Herald Transcript
Quuxplusone added inline comments.
libcxx/include/__format/buffer.h
104–110
@vitaut wrote on D110495:

I think D112361 is a step in the right direction. You can do even better and make it represent a contiguous (not necessarily fixed-size) buffer with a single type-erased reallocation/flush function. Then it can be used to write to contiguous containers like vector and string which is a common case directly avoiding copies. This is basically what {fmt} does.

Charlie Barto also showed MSVC STL doing that approach, in his CppCon talk on Thursday. https://cppcon.digital-medium.co.uk/thursday-recordings/
IIRC, basically they have _Size, _Capacity, virtual void _Grow(); and whenever _Size == _Capacity they call _Grow. I guess I remain fuzzy on the details of what _Grow would actually do for a std::string (does it resize? does it merely reserve?).

Mordante added inline comments.Nov 2 2021, 11:01 AM
libcxx/include/__format/buffer.h
104–110

That looks a lot like what fmt does. I tested with a similar approach, but the virtual call seems to have a measurable impact over the __fun_(__buffer_.begin(), __buffer_it_, __obj_); method.

Mordante updated this revision to Diff 385290.Nov 6 2021, 12:17 PM

Update the design based on the latest feedback.
Still a proof-of-concept to discuss the way ahead.

Note the CI will probably fail since it's based on older CI files.

vitaut added inline comments.Nov 7 2021, 7:11 AM
libcxx/include/__format/buffer.h
63

You might also want to provide an API for appending multiple chars at a time (e.g. a string_view) which can be implemented more efficiently than appending individual characters.

68–69

Wouldn't this overwrite the data for direct storage?

102

Did you mean internal_storage? (missing "n")

Mordante added inline comments.Nov 7 2021, 7:33 AM
libcxx/include/__format/buffer.h
63

I already considered that, but I prefer to do that in a separate commit.
I'll add a TODO FMT in the source to make that intention clear.

68–69

No the flush of the direct storage only adjusts the output iterator. The output iterator needs to be updated when the the direct storage uses a __wrap_iter<_CharT*> instead of a _CharT*.

102

Thanks for catching this typo.

vitaut added inline comments.Nov 7 2021, 8:04 AM
libcxx/include/__format/buffer.h
60–61

Looks like this doesn't need to be a template because it is only called with internal storage.

63

Makes sense.

87–92

Not sure if it matters but __ptr_, __size_ and __capacity_ are accessed way more frequently than __flush_ and __obj_ so maybe put them first?

117–123

__ptr_ and __capacity_ duplicate members of __format_buffer. Is it possible to get rid of them?

203–204

There is a naming inconsistency here (buffer vs writer): the class is called __buffer_selector while it selects between __writer_*.

Mordante marked 9 inline comments as done.Nov 13 2021, 9:13 AM
Mordante added inline comments.
libcxx/include/__format/buffer.h
60–61

Good point, I changed the call to just give the new values for __ptr_ and __capacity_ as argument.

117–123

An interesting observation. I've tested it and these members are indeed not required. This means the entire class can just be an empty class. Since __format_buffer still needs to select between this storage and the __interal_storage it can't be removed.

Mordante updated this revision to Diff 387031.Nov 13 2021, 9:44 AM
Mordante marked 2 inline comments as done.

Addresses review comments.
@vitaut's suggestion turned __direct_storage into an empty class, this avoids some duplication but required a small rewrite.
The CI will fail.

This version will be used to update the earlier patches in this series so this patch can be applied in smaller steps.

vitaut added inline comments.Nov 17 2021, 4:45 PM
libcxx/include/__format/buffer.h
104–110

The virtual call can be replaced with an indirect call (similar to __flush_ in this diff) and it should only be called rarely (normally when you need to do a reallocation). But to see the benefits you really need to make use of writing to the buffer directly. It doesn't make much sense to test with a push_back API which only writes individual characters. I guess the latter is the reason why you even see virtual calls at all. The current approach while an improvement has an extra level of buffering and likely be slower in common scenarios compared to direct output. I think you can even implement the flush method using the grow method + a fixed intermediate buffer so the latter is strictly more powerful and can address cases where an extra buffering helps reducing reallocations.

Mordante planned changes to this revision.Nov 22 2021, 9:09 AM
Mordante marked an inline comment as done.

Please note that the changes in this patch have been applied to the other patches in the stack. So this patch can probably be abandoned.
(For now I keep it open, but remove it from the review queue.)

libcxx/include/__format/buffer.h
104–110

It seems this comment has moved and not really attached to where the comment belongs. I've there changes:

  • A direct buffer (char*, std::vector<char>::begin(), std::string::begin()) writes directly to the underlying character pointer. The flush there is used to keep track of the number of writes. A std::string::iterator is a std::wrap_iter. To return the proper iterator this calculation is done at the end. The direct buffer should only flush once since its capacity is size_t(-1). (For format_to_n the capacity of the buffer is limited to n.)
  • An indirect buffer (all other iterators) write to an internal buffer and are copied to the output during the flush. When it's a std::back_insert_iterator for an container with an insert member it uses insert else it just copies it.

Making the internal buffer a variable size might help. However during testing using a larger internal buffer didn't have a real affect on the benchmarks. This might change when I add insert operations for std::string_view in the buffer. I like to investigate this once I start working on that part.

vitaut added inline comments.Nov 24 2021, 12:11 PM
libcxx/include/__format/buffer.h
104–110

The comment is not attached to something in particular, I was just continuing the discussion started by Arthur. Handling std::vector<char>::begin() directly is fine but it's not the case I was referring to and it's less interesting because of being generally unsafe. The common case is std::back_insert_iterator to a contiguous container and that's where it would be great to avoid an extra buffering. Handling of this case is the main difference between the flush approach from this diff and the grow approach used in {fmt}.

vitaut added inline comments.Nov 25 2021, 8:05 AM
libcxx/include/__format/buffer.h
104–110

Anyway, since "this patch can probably be abandoned", let's move the discussion to other diffs.

Mordante abandoned this revision.Mar 26 2022, 5:57 AM
Mordante marked an inline comment as done.

This patch was mainly intended to discuss the direction and the changes have been applied to other patches in the series.

Herald added a project: Restricted Project. · View Herald TranscriptMar 26 2022, 5:57 AM