Summary: | [WTF] Add Markable<T, Traits> | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Product: | WebKit | Reporter: | Yusuke Suzuki <ysuzuki> | ||||||||||||
Component: | Web Template Framework | Assignee: | Yusuke Suzuki <ysuzuki> | ||||||||||||
Status: | RESOLVED FIXED | ||||||||||||||
Severity: | Normal | CC: | achristensen, commit-queue, darin, ews-watchlist, Hironori.Fujii, mark.lam, saam, sam, simon.fraser, webkit-bug-importer | ||||||||||||
Priority: | P2 | Keywords: | InRadar | ||||||||||||
Version: | WebKit Nightly Build | ||||||||||||||
Hardware: | Unspecified | ||||||||||||||
OS: | Unspecified | ||||||||||||||
Bug Depends on: | |||||||||||||||
Bug Blocks: | 189236, 187460 | ||||||||||||||
Attachments: |
|
Description
Yusuke Suzuki
2018-09-02 07:04:57 PDT
(In reply to Yusuke Suzuki from comment #0) > std::optional<T> is super nice. We can represent a value with nullopt by > using std::optional<T>. > However, as you know, std::optional<T> has storage efficiency problem. It > always has a bool indicating that the value is nullopt or not. > If you have a class like, > > class A { > std::optional<MonotonicTime> m_timeA; > std::optional<MonotonicTime> m_timeB; > std::optional<MonotonicTime> m_timeC; > }; > > This class has significant amount of padding between m_timeA / m_timeB, > m_timeB / m_timeC due to the above bool. > > > If we know that MonotonicTime has a value that represents invalid, we can > use it instead and save the storage. > This is very similar problem to our HashTable implementation. In our > HashTable implementation, we need Deleted / Empty value, which can represent > Deleted and Empty values without sacrificing storage efficiency. > > So, we should have similar mechanism here. In this patch, we have > WTF::CompactOptional<T, Traits>. Traits offers Traits::isEmptyValue() and > the way to generate an empty value. > Then, we use this empty value instead of having bool flag. This way, we can > make `sizeof(WTF::CompactOptional<T>) == sizeof(T)`. > > This idea is inspired from https://github.com/akrzemi1/markable. But we > would like to have WTF::CompactOptional<T> here instead of importing it > since, > > 1. We would like to have more integrated interface to std:optional<T>. We > would like to have CompactOptional(std::optional<T>) constructor. > 2. We would like to integrate existing `isEmptyValue()` mechanism for > HashTable easily into CompactOptional<T>. And we want the interface converting CompactOptional<T> to std::optional<T>. Created attachment 348749 [details]
Patch
Attachment 348749 [details] did not pass style-queue:
ERROR: Source/WTF/wtf/CompactOptional.h:130: Boolean expressions that span multiple lines should have their operators on the left side of the line instead of the right side. [whitespace/operators] [4]
ERROR: Source/WTF/wtf/CompactOptional.h:131: This { should be at the end of the previous line [whitespace/braces] [4]
ERROR: Source/WTF/wtf/CompactOptional.h:138: This { should be at the end of the previous line [whitespace/braces] [4]
Total errors found: 3 in 11 files
If any of these errors are false positives, please file a bug against check-webkit-style.
Created attachment 348750 [details]
Patch
Attachment 348750 [details] did not pass style-queue:
ERROR: Source/WTF/wtf/CompactOptional.h:130: Boolean expressions that span multiple lines should have their operators on the left side of the line instead of the right side. [whitespace/operators] [4]
ERROR: Source/WTF/wtf/CompactOptional.h:131: This { should be at the end of the previous line [whitespace/braces] [4]
ERROR: Source/WTF/wtf/CompactOptional.h:138: This { should be at the end of the previous line [whitespace/braces] [4]
Total errors found: 3 in 13 files
If any of these errors are false positives, please file a bug against check-webkit-style.
Created attachment 348751 [details]
Patch
Attachment 348751 [details] did not pass style-queue:
ERROR: Source/WTF/wtf/CompactOptional.h:130: Boolean expressions that span multiple lines should have their operators on the left side of the line instead of the right side. [whitespace/operators] [4]
ERROR: Source/WTF/wtf/CompactOptional.h:131: This { should be at the end of the previous line [whitespace/braces] [4]
ERROR: Source/WTF/wtf/CompactOptional.h:138: This { should be at the end of the previous line [whitespace/braces] [4]
Total errors found: 3 in 13 files
If any of these errors are false positives, please file a bug against check-webkit-style.
Created attachment 348761 [details]
Patch
Attachment 348761 [details] did not pass style-queue:
ERROR: Source/WTF/wtf/CompactOptional.h:130: Boolean expressions that span multiple lines should have their operators on the left side of the line instead of the right side. [whitespace/operators] [4]
ERROR: Source/WTF/wtf/CompactOptional.h:131: This { should be at the end of the previous line [whitespace/braces] [4]
ERROR: Source/WTF/wtf/CompactOptional.h:138: This { should be at the end of the previous line [whitespace/braces] [4]
Total errors found: 3 in 13 files
If any of these errors are false positives, please file a bug against check-webkit-style.
Sam is working on a class to hold a group of optionals with an OptionSet, which may end up with a similar name, but doesn't use magic values. I wonder if the name of the class in this patch should be more like Markable to avoid confusion? I think CompactOptional is fine for this. The other class will be about multiple optionals so will probably have a different name (and if not, we can rename then). I filed a bug about that idea (plus a proof of concept) at https://bugs.webkit.org/show_bug.cgi?id=189272. (In reply to Sam Weinig from comment #11) > I think CompactOptional is fine for this. The other class will be about > multiple optionals so will probably have a different name (and if not, we > can rename then). I filed a bug about that idea (plus a proof of concept) at > https://bugs.webkit.org/show_bug.cgi?id=189272. Either is OK to me. The name CompactOptional is aligned to the name of WTF::CompactPointerTuple. CompactOptional is effective if the T has a sparse value, or T includes a failure value. Otherwise, std::optional<> or Sam's set are effective! Ping? Created attachment 349286 [details]
Patch
Attachment 349286 [details] did not pass style-queue:
ERROR: Source/WTF/wtf/Markable.h:130: Boolean expressions that span multiple lines should have their operators on the left side of the line instead of the right side. [whitespace/operators] [4]
ERROR: Source/WTF/wtf/Markable.h:131: This { should be at the end of the previous line [whitespace/braces] [4]
ERROR: Source/WTF/wtf/Markable.h:138: This { should be at the end of the previous line [whitespace/braces] [4]
Total errors found: 3 in 13 files
If any of these errors are false positives, please file a bug against check-webkit-style.
Comment on attachment 349286 [details]
Patch
Thanks!
Comment on attachment 349286 [details] Patch Clearing flags on attachment: 349286 Committed r235852: <https://trac.webkit.org/changeset/235852> All reviewed patches have been landed. Closing bug. I think we need to re-visting the name Markable<>. Markable<> sounds too much like it's related to GC marking. (In reply to Simon Fraser (smfr) from comment #20) > I think we need to re-visting the name Markable<>. Markable<> sounds too > much like it's related to GC marking. Is CompactOptional better? (In reply to Yusuke Suzuki from comment #21) > (In reply to Simon Fraser (smfr) from comment #20) > > I think we need to re-visting the name Markable<>. Markable<> sounds too > > much like it's related to GC marking. > > Is CompactOptional better? Somewhat, but it would be nice to find a name that communicate the fact that this kind of optional requires magic values. Maybe ReservedValueOptional<>? (In reply to Simon Fraser (smfr) from comment #22) > (In reply to Yusuke Suzuki from comment #21) > > (In reply to Simon Fraser (smfr) from comment #20) > > > I think we need to re-visting the name Markable<>. Markable<> sounds too > > > much like it's related to GC marking. > > > > Is CompactOptional better? > > Somewhat, but it would be nice to find a name that communicate the fact that > this kind of optional requires magic values. Maybe ReservedValueOptional<>? Or IntrusiveOptional? (since empty optional value is intrusively implemented by the type T). |