Bug 189231 – [WTF] Add Markable<T, Traits>

• Component: Web Template Framework
• Status: RESOLVED FIXED

[Yusuke Suzuki]

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>.

[Yusuke Suzuki]

(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>.

[Yusuke Suzuki]

Created attachment 348749 [details]
Patch

[EWS Watchlist]

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.

[Yusuke Suzuki]

Created attachment 348750 [details]
Patch

[EWS Watchlist]

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.

[Yusuke Suzuki]

Created attachment 348751 [details]
Patch

[EWS Watchlist]

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.

[Yusuke Suzuki]

Created attachment 348761 [details]
Patch

[EWS Watchlist]

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.

[Simon Fraser (smfr)]

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?

[Sam Weinig]

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.

[Yusuke Suzuki]

(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!

[Yusuke Suzuki]

Ping?

[Yusuke Suzuki]

Created attachment 349286 [details]
Patch

[EWS Watchlist]

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.

[Yusuke Suzuki]

Comment on attachment 349286 [details]
Patch

Thanks!

[WebKit Commit Bot]

Comment on attachment 349286 [details]
Patch

Clearing flags on attachment: 349286

Committed r235852: <https://trac.webkit.org/changeset/235852>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Radar WebKit Bug Importer]

<rdar://problem/44310013>

[Simon Fraser (smfr)]

I think we need to re-visting the name Markable<>. Markable<> sounds too much like it's related to GC marking.

[Yusuke Suzuki]

(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?

[Simon Fraser (smfr)]

(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<>?

[Yusuke Suzuki]

(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).