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>.
(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.
<rdar://problem/44310013>
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).