[prev in list] [next in list] [prev in thread] [next in thread]
List: kde-frameworks-devel
Subject: Re: D26126: Simplify param method: Return Early, Use a Map and Assert.
From: Tomaz Canabrava <tcanabrava () kde ! org>
Date: 2019-12-24 11:04:36
Message-ID: CACk01_xAp7ODRnTN+8K9a5NEWjJRG8g0bnq+tf_eniBAEXbEbA () mail ! gmail ! com
[Download RAW message or body]
David,
Thanks for the detailed explanation, I'm currently reworking most of the
patches here. About the optimizations - I know the linear search is a bad
optimization, but it adds legibility, that's what I tried to do.
I tried to emulate the python `if value in vector` that is really easy to
read, compared to the current code.
On Tue, Dec 24, 2019 at 9:40 AM David Faure <noreply@phabricator.kde.org>
wrote:
> dfaure requested changes to this revision.
> dfaure added inline comments. View Revision
> <https://phabricator.kde.org/D26126>
> *INLINE COMMENTS*
> View Inline <https://phabricator.kde.org/D26126#inline-147537>
> kconfig_compiler.cpp:1020
> } else if (type == QLatin1String("font")) {
> return QStringLiteral("const QFont &");
> } else if (type == QLatin1String("rect")) {
> QLatin1String("double")}
> ).contains(type)) {
> return type;
>
> This linear search doesn't look like an optimization to me. It would be
> better to incorporate this into the map, so that a single search is
> performed, rather than two.
>
> View Inline <https://phabricator.kde.org/D26126#inline-147473>ervin wrote
> in kconfig_compiler.cpp:1024
>
> std::map looks like a bad idea here, either use QHash (preferred in
> massively based Qt code) or std::unordered_map.
>
> Also for both temporaries you pay the price of their allocation and
> deallocation at each call. Even a mutex used at each call would do better.
> ;-)
>
> I'm not 100% sure about std::map vs QHash given the number of elements,
> this would need benchmarking.
>
> But I agree 100% that compiler-generated thread safety around a static is
> NOTHING compared to amount of nodes allocated to fill in a map or hash.
>
> @tcanabrava <https://phabricator.kde.org/p/tcanabrava/> Please have a
> look at https://gist.github.com/jboner/2841832
> Locking an available mutex is 4 times faster than even fetching data from
> main memory (i.e. data which isn't yet in a CPU cache). This is many orders
> of magnitude faster than creating a filling a map or a hash full of
> QStrings. On top of that, compilers don't even generate a full-blown mutex
> for threadsafe statics, they generate a three-state atomic (a bit like
> Q_GLOBAL_STATIC does) (3 because not created, being created, already
> created).
>
> The most performant solution is to turn the input string into a QByteArray
> and then perform a binary search in a C array of const char* (no
> allocations, even the very first time).
> The most readable (but still good, unlike the current code in git)
> solution is a static map.
>
> *REPOSITORY*
> R237 KConfig
>
> *REVISION DETAIL*
> https://phabricator.kde.org/D26126
>
> *To: *tcanabrava, ervin, dfaure
> *Cc: *dfaure, ervin, GB_2, apol, kde-frameworks-devel, LeGast00n,
> michaelh, ngraham, bruns
>
[Attachment #3 (text/html)]
<div dir="ltr"><div>David,</div><div><br></div><div>Thanks for the detailed \
explanation, I'm currently reworking most of the patches here. About the \
optimizations - I know the linear search is a bad optimization, but it adds \
legibility, that's what I tried to do.</div><div>I tried to emulate the python \
`if value in vector` that is really easy to read, compared to the current \
code.</div><div><br></div><div><br></div></div><br><div class="gmail_quote"><div \
dir="ltr" class="gmail_attr">On Tue, Dec 24, 2019 at 9:40 AM David Faure <<a \
href="mailto:noreply@phabricator.kde.org">noreply@phabricator.kde.org</a>> \
wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px \
0.8ex;border-left:1px solid \
rgb(204,204,204);padding-left:1ex"><table><tbody><tr><td>dfaure requested changes to \
this revision.<br>dfaure added inline comments. </td><td><a \
style="text-decoration:none;padding:4px 8px;margin:0px 8px \
8px;float:right;color:rgb(70,76,92);font-weight:bold;border-radius:3px;background-colo \
r:rgb(247,247,249);background-image:linear-gradient(rgb(255,255,255),rgb(241,240,241));display:inline-block;border:1px \
solid rgba(71,87,120,0.2)" href="https://phabricator.kde.org/D26126" \
target="_blank">View Revision</a></td></tr></tbody></table><br><div><strong>INLINE \
COMMENTS</strong><div><div style="margin:6px 0px 12px"><div style="border:1px solid \
rgb(199,204,217);border-radius:3px"><div \
style="padding:0px;background:rgb(247,247,247) none repeat scroll 0% \
0%;border-color:rgb(227,228,232);border-style:solid;border-width:0px 0px \
1px;margin:0px"><div style="color:rgb(116,119,125);background:rgb(239,242,244) none \
repeat scroll 0% 0%;padding:6px 8px;overflow:hidden"><a \
style="float:right;text-decoration:none" \
href="https://phabricator.kde.org/D26126#inline-147537" target="_blank">View \
Inline</a><span style="color:rgb(75,77,81);font-weight:bold">kconfig_compiler.cpp:1020</span></div>
<div style="font:11px/15px \
"Menlo","Consolas","Monaco",monospace;white-space:pre-wrap;clear:both;padding:4px \
0px;margin:0px"><div style="padding:0px 8px;margin:0px \
4px;background:rgba(251,175,175,0.7) none repeat scroll 0% 0%"> \
<span></span><span><span>}</span></span><span> </span><span \
style="color:rgb(170,64,0)"><span>else</span></span><span> </span><span \
style="color:rgb(170,64,0)"><span>if</span></span><span> \
</span><span><span>(</span></span><span></span><span><span>type</span></span><span> \
</span><span style="color:rgb(170,34,17)"><span>==</span></span> \
<span>QLatin1String</span><span>(</span><span \
style="color:rgb(118,101,16)">"<span>font"</span></span><span></span><span><span>))</span></span><span> \
</span><span><span>{</span></span> </div><div style="padding:0px 8px;margin:0px \
4px;background:rgba(251,175,175,0.7) none repeat scroll 0% 0%"> \
<span></span><span style="color:rgb(170,64,0)"><span>return</span></span><span> \
</span><span><span>QStringLiteral</span></span><span></span><span><span>(</span></span><span></span><span \
style="color:rgb(118,101,16)"><span>"const QFont \
&"</span></span><span></span><span><span>);</span></span> </div><div \
style="padding:0px 8px;margin:0px 4px;background:rgba(251,175,175,0.7) none repeat \
scroll 0% 0%"> <span></span><span><span>}</span></span><span> </span><span \
style="color:rgb(170,64,0)"><span>else</span></span><span> </span><span \
style="color:rgb(170,64,0)"><span>if</span></span><span> \
</span><span><span>(</span></span><span></span><span><span>type</span></span><span> \
</span><span style="color:rgb(170,34,17)"><span>==</span></span><span> \
</span><span><span>QLatin1String</span></span><span></span><span><span>(</span></span><span></span><span \
style="color:rgb(118,101,16)"><span>"rect"</span></span><span></span><span><span>))</span></span><span> \
</span><span><span>{</span></span> </div><div style="padding:0px 8px;margin:0px \
4px;background:rgba(151,234,151,0.6) none repeat scroll 0% 0%"> <span> \
</span> <span>QLatin1String</span><span>(</span><span \
style="color:rgb(118,101,16)">"<span>double"</span></span><span></span><span><span>)}</span></span>
</div><div style="padding:0px 8px;margin:0px 4px;background:rgba(151,234,151,0.6) \
none repeat scroll 0% 0%"> \
<span></span><span><span>).</span></span><span></span><span><span>contains</span></spa \
n><span></span><span><span>(</span></span><span></span><span><span>type</span></span><span></span><span><span>))</span></span><span> \
</span><span><span>{</span></span> </div><div style="padding:0px 8px;margin:0px \
4px;background:rgba(151,234,151,0.6) none repeat scroll 0% 0%"> <span> \
</span><span style="color:rgb(170,64,0)"><span>return</span></span><span> \
</span><span><span>type</span></span><span></span><span><span>;</span></span> \
</div></div></div> <div style="margin:8px 0px;padding:0px 12px"><p \
style="padding:0px;margin:8px">This linear search doesn't look like an \
optimization to me. It would be better to incorporate this into the map, so that a \
single search is performed, rather than two.</p></div></div><br><div \
style="border:1px solid rgb(199,204,217);border-radius:3px"><div \
style="padding:0px;background:rgb(247,247,247) none repeat scroll 0% \
0%;border-color:rgb(227,228,232);border-style:solid;border-width:0px 0px \
1px;margin:0px"><div style="color:rgb(116,119,125);background:rgb(239,242,244) none \
repeat scroll 0% 0%;padding:6px 8px;overflow:hidden"><a \
style="float:right;text-decoration:none" \
href="https://phabricator.kde.org/D26126#inline-147473" target="_blank">View \
Inline</a><span style="color:rgb(75,77,81);font-weight:bold">ervin</span> wrote in \
<span style="color:rgb(75,77,81);font-weight:bold">kconfig_compiler.cpp:1024</span></div>
<div style="margin:8px 0px;padding:0px 12px;color:rgb(116,119,125)"><p \
style="padding:0px;margin:8px">std::map looks like a bad idea here, either use QHash \
(preferred in massively based Qt code) or std::unordered_map.</p>
<p style="padding:0px;margin:8px">Also for both temporaries you pay the price of \
their allocation and deallocation at each call. Even a mutex used at each call would \
do better. ;-)</p></div></div> <div style="margin:8px 0px;padding:0px 12px"><p \
style="padding:0px;margin:8px">I'm not 100% sure about std::map vs QHash given \
the number of elements, this would need benchmarking.</p>
<p style="padding:0px;margin:8px">But I agree 100% that compiler-generated thread \
safety around a static is NOTHING compared to amount of nodes allocated to fill in a \
map or hash.</p>
<p style="padding:0px;margin:8px"><a href="https://phabricator.kde.org/p/tcanabrava/" \
style="color:rgb(25,85,141);background-color:rgb(241,247,255);border:1px solid \
transparent;border-radius:3px;font-weight:bold;padding:0px 4px" \
target="_blank">@tcanabrava</a> Please have a look at <a \
href="https://gist.github.com/jboner/2841832" rel="noreferrer" \
target="_blank">https://gist.github.com/jboner/2841832</a><br> Locking an available \
mutex is 4 times faster than even fetching data from main memory (i.e. data which \
isn't yet in a CPU cache). This is many orders of magnitude faster than creating \
a filling a map or a hash full of QStrings. On top of that, compilers don't even \
generate a full-blown mutex for threadsafe statics, they generate a three-state \
atomic (a bit like Q_GLOBAL_STATIC does) (3 because not created, being created, \
already created).</p>
<p style="padding:0px;margin:8px">The most performant solution is to turn the input \
string into a QByteArray and then perform a binary search in a C array of const char* \
(no allocations, even the very first time).<br> The most readable (but still good, \
unlike the current code in git) solution is a static \
map.</p></div></div></div></div></div><br><div><strong>REPOSITORY</strong><div><div>R237 \
KConfig</div></div></div><br><div><strong>REVISION DETAIL</strong><div><a \
href="https://phabricator.kde.org/D26126" \
target="_blank">https://phabricator.kde.org/D26126</a></div></div><br><div><strong>To: \
</strong>tcanabrava, ervin, dfaure<br><strong>Cc: </strong>dfaure, ervin, GB_2, apol, \
kde-frameworks-devel, LeGast00n, michaelh, ngraham, \
bruns<br></div></blockquote></div>
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic