Reduce wait times for very large PEXE files.

Reduce wait times for very large PEXE files.

Investigated how many parser waits occur when the OptQ fills up. The
current implementation has 64k entries, which for 10Mb examples, never
fill up (but do come close to filling up).

To test, I dropped the queue size down. The numbers I got was that the
queue size plus the number of parse waits was within 2% of the total
number of function blocks. Hence, once OptQ fills up a lot of slow
notifies get applied.

Hence, for scaling, I modifed the code to not wake up the parse thread
(during a pop) until OptQ got half empty. The results were that once
the Opt got up to size 1024, less than 100 notifies would be
issued. From 1024 on, as the queue size doubled, the number of
notifies would drop roughly in half.

Based on this, I decided to add the feature that the OptQ did not wake
up the waiting parse thread until half empty. Since the queue size was
not shrunk, this CL shouldn't add any overhead for the PEXES we have,
and very few waits with significantly largers than the current (10Mb)
PEXES.

BUG=None
R=jpp@chromium.org

Committed: https://gerrit.chromium.org/gerrit/gitweb?p=native_client/pnacl-subzero.git;a=commit;h=3018cf2b3e0b58a13b6b1e31cb27c5f0a7fd0c37

[Karl, 2016-04-11 15:45:01]

Description was changed from

==========
Reduce wait times for very large PEXE files.

Investigated how many parser waits occur when the OptQ fills up. The
current implementation has 64k entries, which for 10Mb examples, never
fill up (but do come close to filling up).

To test, I dropped the queue size down. The numbers I got was that the
queue size plus the number of parse waits was within 2% of the total
number of function blocks. Hence, once OptQ fills up a lot of slow
notifies get applied.

Hence, for scaling, I modifed the code to not wake up the parse thread
(during a pop) until OptQ got half empty. The results were that once
the Opt got up to size 1024, less than 100 notifies would be
issued. From 1024 on, as the queue size doubled, the number of
notifies would drop roughly in half.

Based on this, I decided to add the feature that the OptQ did not wake
up the waiting parse thread until half empty. Since the queue size was
not shrunk, this CL shouldn't add any overhead for the PEXES we have,
and very few waits with significantly largers than the current (10Mb)
PEXES.

BUG=None
==========

to

==========
Reduce wait times for very large PEXE files.

Investigated how many parser waits occur when the OptQ fills up. The
current implementation has 64k entries, which for 10Mb examples, never
fill up (but do come close to filling up).

To test, I dropped the queue size down. The numbers I got was that the
queue size plus the number of parse waits was within 2% of the total
number of function blocks. Hence, once OptQ fills up a lot of slow
notifies get applied.

Hence, for scaling, I modifed the code to not wake up the parse thread
(during a pop) until OptQ got half empty. The results were that once
the Opt got up to size 1024, less than 100 notifies would be
issued. From 1024 on, as the queue size doubled, the number of
notifies would drop roughly in half.

Based on this, I decided to add the feature that the OptQ did not wake
up the waiting parse thread until half empty. Since the queue size was
not shrunk, this CL shouldn't add any overhead for the PEXES we have,
and very few waits with significantly largers than the current (10Mb)
PEXES.

BUG=None
==========

[Karl, 2016-04-11 15:45:01]

kschimpf@google.com changed reviewers:
+ eholk@chromium.org, jpp@chromium.org, sehr@chromium.org, stichnot@chromium.org

[John, 2016-04-11 16:28:00]

lgtm

https://codereview.chromium.org/1877873002/diff/20001/src/IceGlobalContext.cpp
File src/IceGlobalContext.cpp (right):

https://codereview.chromium.org/1877873002/diff/20001/src/IceGlobalContext.cp...
src/IceGlobalContext.cpp:952: return
std::unique_ptr<OptWorkItem>(OptQ.blockingPop(OptQWakeupSize));
Not really your fault, but can you remove the

std::unique_ptr<OptWorkItem>()

ctor call? It is not needed... I think. :)

https://codereview.chromium.org/1877873002/diff/20001/src/IceGlobalContext.h
File src/IceGlobalContext.h (right):

https://codereview.chromium.org/1877873002/diff/20001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:483: static constexpr size_t MaxOptQSize = 1 << 16;
Can this be moved to the .cpp file? I see no uses of it, except in
IceGlobalContext.cpp

[Jim Stichnoth, 2016-04-11 16:46:09]

Quick drive-by since I'm on vacation.

Consider using this bug:
https://bugs.chromium.org/p/nativeclient/issues/detail?id=4081

Have you stress-tested this by setting the queue size to 2, or 4, or 8, or ...,
and then running with lots of threads?  I'm concerned about race conditions /
deadlocks since I ran into such problems in past experiments.

[Karl, 2016-04-11 21:48:54]

I have checked out if it works for small sizes, with large thread pointers. I
did not find any issues.

The key to not effecting anything is to realize that we only halve the size if
it is larger than the number of threads. Otherwise, we exercise the code in the
same manner as before this CL.

https://codereview.chromium.org/1877873002/diff/20001/src/IceGlobalContext.cpp
File src/IceGlobalContext.cpp (right):

https://codereview.chromium.org/1877873002/diff/20001/src/IceGlobalContext.cp...
src/IceGlobalContext.cpp:952: return
std::unique_ptr<OptWorkItem>(OptQ.blockingPop(OptQWakeupSize));
On 2016/04/11 16:27:59, John wrote:
> Not really your fault, but can you remove the
> 
> std::unique_ptr<OptWorkItem>()
> 
> ctor call? It is not needed... I think. :)

Done.

https://codereview.chromium.org/1877873002/diff/20001/src/IceGlobalContext.h
File src/IceGlobalContext.h (right):

https://codereview.chromium.org/1877873002/diff/20001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:483: static constexpr size_t MaxOptQSize = 1 << 16;
On 2016/04/11 16:28:00, John wrote:
> Can this be moved to the .cpp file? I see no uses of it, except in
> IceGlobalContext.cpp

It is used to define OptQ below.

[Karl, 2016-04-11 21:49:04]

Description was changed from

==========
Reduce wait times for very large PEXE files.

Investigated how many parser waits occur when the OptQ fills up. The
current implementation has 64k entries, which for 10Mb examples, never
fill up (but do come close to filling up).

To test, I dropped the queue size down. The numbers I got was that the
queue size plus the number of parse waits was within 2% of the total
number of function blocks. Hence, once OptQ fills up a lot of slow
notifies get applied.

Hence, for scaling, I modifed the code to not wake up the parse thread
(during a pop) until OptQ got half empty. The results were that once
the Opt got up to size 1024, less than 100 notifies would be
issued. From 1024 on, as the queue size doubled, the number of
notifies would drop roughly in half.

Based on this, I decided to add the feature that the OptQ did not wake
up the waiting parse thread until half empty. Since the queue size was
not shrunk, this CL shouldn't add any overhead for the PEXES we have,
and very few waits with significantly largers than the current (10Mb)
PEXES.

BUG=None
==========

to

==========
Reduce wait times for very large PEXE files.

Investigated how many parser waits occur when the OptQ fills up. The
current implementation has 64k entries, which for 10Mb examples, never
fill up (but do come close to filling up).

To test, I dropped the queue size down. The numbers I got was that the
queue size plus the number of parse waits was within 2% of the total
number of function blocks. Hence, once OptQ fills up a lot of slow
notifies get applied.

Hence, for scaling, I modifed the code to not wake up the parse thread
(during a pop) until OptQ got half empty. The results were that once
the Opt got up to size 1024, less than 100 notifies would be
issued. From 1024 on, as the queue size doubled, the number of
notifies would drop roughly in half.

Based on this, I decided to add the feature that the OptQ did not wake
up the waiting parse thread until half empty. Since the queue size was
not shrunk, this CL shouldn't add any overhead for the PEXES we have,
and very few waits with significantly largers than the current (10Mb)
PEXES.

BUG=None
R=jpp@chromium.org

Committed:
https://gerrit.chromium.org/gerrit/gitweb?p=native_client/pnacl-subzero.git;a...
==========

[Karl, 2016-04-11 21:49:06]

Committed patchset #3 (id:40001) manually as
3018cf2b3e0b58a13b6b1e31cb27c5f0a7fd0c37 (presubmit successful).

[Jim Stichnoth, 2016-04-13 15:33:19]

https://codereview.chromium.org/1877873002/diff/40001/src/IceGlobalContext.h
File src/IceGlobalContext.h (right):

https://codereview.chromium.org/1877873002/diff/40001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:480: /// Number of function blocks that can be queued
before waiting for
reflow comment

https://codereview.chromium.org/1877873002/diff/40001/src/IceThreading.h
File src/IceThreading.h (right):

https://codereview.chromium.org/1877873002/diff/40001/src/IceThreading.h#newc...
src/IceThreading.h:70: std::unique_ptr<T> blockingPop(size_t
NotifyWhenDownToSize = MaxStaticSize) {
Would it make sense to also apply this to blockingPush() onto the emit queue? 
The emit thread presumably also spends a lot of its time blocked waiting for
more work items, so the translator thread spends significant time notifying and
unblocking the emit thread.