Bug 189231 - [WTF] Add Markable<T, Traits>
Summary: [WTF] Add Markable<T, Traits>
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: Web Template Framework (show other bugs)
Version: WebKit Nightly Build
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Yusuke Suzuki
URL:
Keywords: InRadar
Depends on:
Blocks: 187460 189236
  Show dependency treegraph
 
Reported: 2018-09-02 07:04 PDT by Yusuke Suzuki
Modified: 2018-09-11 08:54 PDT (History)
10 users (show)

See Also:


Attachments
Patch (24.65 KB, patch)
2018-09-02 12:49 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Patch (30.51 KB, patch)
2018-09-02 12:58 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Patch (30.50 KB, patch)
2018-09-02 13:47 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Patch (30.48 KB, patch)
2018-09-03 01:33 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Patch (29.72 KB, patch)
2018-09-09 07:35 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Yusuke Suzuki 2018-09-02 07:04:57 PDT
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>.
Comment 1 Yusuke Suzuki 2018-09-02 07:07:37 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>.
Comment 2 Yusuke Suzuki 2018-09-02 12:49:09 PDT
Created attachment 348749 [details]
Patch
Comment 3 EWS Watchlist 2018-09-02 12:51:58 PDT
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.
Comment 4 Yusuke Suzuki 2018-09-02 12:58:24 PDT
Created attachment 348750 [details]
Patch
Comment 5 EWS Watchlist 2018-09-02 12:59:55 PDT
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.
Comment 6 Yusuke Suzuki 2018-09-02 13:47:17 PDT
Created attachment 348751 [details]
Patch
Comment 7 EWS Watchlist 2018-09-02 13:49:10 PDT
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.
Comment 8 Yusuke Suzuki 2018-09-03 01:33:28 PDT
Created attachment 348761 [details]
Patch
Comment 9 EWS Watchlist 2018-09-03 01:35:04 PDT
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.
Comment 10 Simon Fraser (smfr) 2018-09-04 08:38:00 PDT
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?
Comment 11 Sam Weinig 2018-09-04 13:54:31 PDT
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.
Comment 12 Yusuke Suzuki 2018-09-06 03:35:42 PDT
(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!
Comment 13 Yusuke Suzuki 2018-09-09 07:28:48 PDT
Ping?
Comment 14 Yusuke Suzuki 2018-09-09 07:35:33 PDT
Created attachment 349286 [details]
Patch
Comment 15 EWS Watchlist 2018-09-09 07:39:30 PDT
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 16 Yusuke Suzuki 2018-09-10 10:52:04 PDT
Comment on attachment 349286 [details]
Patch

Thanks!
Comment 17 WebKit Commit Bot 2018-09-10 11:19:18 PDT
Comment on attachment 349286 [details]
Patch

Clearing flags on attachment: 349286

Committed r235852: <https://trac.webkit.org/changeset/235852>
Comment 18 WebKit Commit Bot 2018-09-10 11:19:20 PDT
All reviewed patches have been landed.  Closing bug.
Comment 19 Radar WebKit Bug Importer 2018-09-10 11:20:25 PDT
<rdar://problem/44310013>
Comment 20 Simon Fraser (smfr) 2018-09-10 14:06:43 PDT
I think we need to re-visting the name Markable<>. Markable<> sounds too much like it's related to GC marking.
Comment 21 Yusuke Suzuki 2018-09-11 02:57:56 PDT
(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?
Comment 22 Simon Fraser (smfr) 2018-09-11 08:30:29 PDT
(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<>?
Comment 23 Yusuke Suzuki 2018-09-11 08:54:37 PDT
(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).