Subzero: Initial implementation of multithreaded translation.

Subzero: Initial implementation of multithreaded translation.

Provides a single-producer, multiple-consumer translation queue where the number of translation threads is given by the -threads=N argument.  The producer (i.e., bitcode parser) blocks if the queue size is >=N, in order to control the memory footprint.  If N=0 (which is the default), execution is purely single-threaded.  If N=1, there is a single translation thread running in parallel with the parser thread.  "make check" succeeds with the default changed to N=1.

Currently emission is also done by the translation thread, which limits scalability since the emit stream has to be locked.  Also, since the ELF writer stream is not locked, it won't be safe to use N>1 with the ELF writer.  Furthermore, for N>1, emitted function ordering is nondeterministic and needs to be recombobulated.  This will all be fixed in a follow-on CL.

The -timing option is broken for N>0.  This will be fixed in a follow-on CL.

Verbose flags are now managed in the Cfg instead of (or in addition to) the GlobalContext, due to the -verbose-focus option which wants to temporarily change the verbose level for a particular function.

TargetLowering::emitConstants() and related methods are changed to be static, so that a valid TargetLowering object isn't required.  This is because the TargetLowering object wants to hold a valid Cfg, and none really exists after all functions are translated and the constant pool is ready for emission.

The Makefile.standalone now has a TSAN=1 option to enable ThreadSanitizer.

BUG= none
R=jfb@chromium.org

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

[Jim Stichnoth, 2015-01-22 19:09:40]

stichnot@chromium.org changed reviewers:
+ jfb@chromium.org, jvoung@chromium.org, kschimpf@google.com

[Jim Stichnoth, 2015-01-22 19:10:29]

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

https://codereview.chromium.org/870653002/diff/20001/src/IceGlobalContext.cpp...
src/IceGlobalContext.cpp:155: resetStats();
Most of this function was moved from Translator::translateFcn() in
IceTranslator.cpp.

https://codereview.chromium.org/870653002/diff/20001/tests_lit/llvm2ice_tests...
File tests_lit/llvm2ice_tests/nacl-atomic-errors.ll (right):

https://codereview.chromium.org/870653002/diff/20001/tests_lit/llvm2ice_tests...
tests_lit/llvm2ice_tests/nacl-atomic-errors.ll:4: ; RUN: %p2i -i %s --args
--verbose none --exit-success 2>&1 | FileCheck %s
The shellcmd python function throws an exception when llvm2ice returns a nonzero
result.  Previously, this happened to be OK because the error message was being
sent to stderr which was being passed through to FileCheck, but this CL changes
error output to go to the dump stream instead of hard-coded std::cerr.

[Karl, 2015-01-22 20:41:13]

https://codereview.chromium.org/870653002/diff/20001/src/IceTranslator.h
File src/IceTranslator.h (left):

https://codereview.chromium.org/870653002/diff/20001/src/IceTranslator.h#oldc...
src/IceTranslator.h:86: std::unique_ptr<Cfg> Func;
Nice to see this wart go away!

https://codereview.chromium.org/870653002/diff/20001/src/llvm2ice.cpp
File src/llvm2ice.cpp (right):

https://codereview.chromium.org/870653002/diff/20001/src/llvm2ice.cpp#newcode210
src/llvm2ice.cpp:210: static cl::alias SplitModule("split-module",
cl::desc("Alias for -threads"),
Not sure this can be an alias. Single threaded for pnacl-llc assume
split-module=1?

[JF, 2015-01-22 20:50:56]

It would be much better if the verbose change were separate from the
multithreading change.

What's the current speedup from this code?

You should really get a tsan bot up and running before this goes in, otherwise
we're flying blind.

https://codereview.chromium.org/870653002/diff/20001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/870653002/diff/20001/src/IceCfg.cpp#newcode49
src/IceCfg.cpp:49: Cfg::~Cfg() { CurrentCfg = nullptr; }
Comment that this is TLS.

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

https://codereview.chromium.org/870653002/diff/20001/src/IceGlobalContext.cpp...
src/IceGlobalContext.cpp:161: Func->dump();
What are the above two for?

https://codereview.chromium.org/870653002/diff/20001/src/IceGlobalContext.cpp...
src/IceGlobalContext.cpp:167: ErrorStatus = true;
Should the thread continue when it has errors? Shouldn't the errors be in a
container otherwise (so you know how many you received, and what they were)?

https://codereview.chromium.org/870653002/diff/20001/src/IceGlobalContext.cpp...
src/IceGlobalContext.cpp:175: dumpStats(Func->getFunctionName());
I think the stats should be joined at the end of the translation thread, and
kept in TLS during translation.

https://codereview.chromium.org/870653002/diff/20001/src/IceGlobalContext.cpp...
src/IceGlobalContext.cpp:177: delete Func;
Could you use unique_ptr so that you don't need to delete manually?

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

https://codereview.chromium.org/870653002/diff/20001/src/IceGlobalContext.h#n...
src/IceGlobalContext.h:105: std::unique_lock<GlobalLockType> L(Lock);
Can you add a comment on CfgQueue explaining the locking approach for the
producer/consumer? I don't find this intuitive to read, even with the comments
on the members below.

I would also allow more Cfgs to be enqueued than there are workers: that's what
the PNaCl translator does because often functions are very small, so the
consumers dequeue something like 10 functions at at time. This should be a knob
that we can tune later.

https://codereview.chromium.org/870653002/diff/20001/src/IceGlobalContext.h#n...
src/IceGlobalContext.h:141: std::queue<Cfg *> WorkQueue;
This should probably be an std::array if the size is constant.

https://codereview.chromium.org/870653002/diff/20001/src/IceGlobalContext.h#n...
src/IceGlobalContext.h:152: const uint32_t NumWorkers;
I'd make this a size_t.

https://codereview.chromium.org/870653002/diff/20001/src/IceGlobalContext.h#n...
src/IceGlobalContext.h:291: // just exit).
"probably"? That seems mostly accurate.

https://codereview.chromium.org/870653002/diff/20001/src/IceGlobalContext.h#n...
src/IceGlobalContext.h:305: // TODO(stichnot): start emitter thread
?

https://codereview.chromium.org/870653002/diff/20001/src/IceGlobalContext.h#n...
src/IceGlobalContext.h:333: }
I don't understand what this is for.

https://codereview.chromium.org/870653002/diff/20001/src/IceGlobalContext.h#n...
src/IceGlobalContext.h:364: bool ErrorStatus;
Use std::error_code?

https://codereview.chromium.org/870653002/diff/20001/src/IceTargetLowering.cpp
File src/IceTargetLowering.cpp (right):

https://codereview.chromium.org/870653002/diff/20001/src/IceTargetLowering.cp...
src/IceTargetLowering.cpp:107: Ctx->waitForWorkerThreads();
It seems somewhat obscure to have emitConstants be the one that blocks and waits
for the worker threads. I'd instead have a higher level function which starts
the threads, enqueues work, waits for the threads, and then emits constants and
others.

https://codereview.chromium.org/870653002/diff/20001/src/IceTargetLoweringX86...
File src/IceTargetLoweringX8632.h (right):

https://codereview.chromium.org/870653002/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.h:59: static void emitConstants(GlobalContext *Ctx);
Why not keep this as override, and implement per target?

I wouldn't go the static route, I'd instead do static polymorphism through
templates (which is easy to move towards from virtual functions).

https://codereview.chromium.org/870653002/diff/20001/src/llvm2ice.cpp
File src/llvm2ice.cpp (right):

https://codereview.chromium.org/870653002/diff/20001/src/llvm2ice.cpp#newcode209
src/llvm2ice.cpp:209: cl::init(0));
This should default to std::thread::hardware_concurrency.

It's a bit confusing to have 0 and 1 be sequential, though 1 does generate a
thread whereas 0 doesn't.

https://codereview.chromium.org/870653002/diff/20001/src/llvm2ice.cpp#newcode210
src/llvm2ice.cpp:210: static cl::alias SplitModule("split-module",
cl::desc("Alias for -threads"),
On 2015/01/22 20:41:13, Karl wrote:
> Not sure this can be an alias. Single threaded for pnacl-llc assume
> split-module=1?

Why add the alias at all?

https://codereview.chromium.org/870653002/diff/20001/src/llvm2ice.cpp#newcode364
src/llvm2ice.cpp:364: int ErrorStatus = 0;
This should also be an std::vector<std::error_code>.

[JF, 2015-01-22 21:12:14]

Also, does the current code emit deterministic output when multithreaded? It
should at east have an option such as -in-order-recombobulator.

[Jim Stichnoth, 2015-01-22 21:26:32]

On 2015/01/22 21:12:14, JF wrote:
> Also, does the current code emit deterministic output when multithreaded? It
> should at east have an option such as -in-order-recombobulator.

Currently it only discombobulates nondeterminstically as mentioned in the CL
description.

The follow-on CL will handle code emission in a separate thread, using a
multiple-writer/single-reader queue.  The output will always be
deterministically recombobulated (unless, say, code randomization).

[jvoung (off chromium), 2015-01-22 23:06:06]

Not much to add =)

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

https://codereview.chromium.org/870653002/diff/20001/src/IceGlobalContext.cpp...
src/IceGlobalContext.cpp:498: return;
Could report_fatal_error for now?

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

https://codereview.chromium.org/870653002/diff/20001/src/IceGlobalContext.h#n...
src/IceGlobalContext.h:105: std::unique_lock<GlobalLockType> L(Lock);
On 2015/01/22 20:50:56, JF wrote:
> Can you add a comment on CfgQueue explaining the locking approach for the
> producer/consumer? I don't find this intuitive to read, even with the comments
> on the members below.
> 
> I would also allow more Cfgs to be enqueued than there are workers: that's
what
> the PNaCl translator does because often functions are very small, so the
> consumers dequeue something like 10 functions at at time. This should be a
knob
> that we can tune later.


Yeah, for pnacl-llc, it dequeues N functions at a time, where the N starts at
like 8 or 10, but the N tapers down to 1 near the end.

https://codereview.chromium.org/870653002/diff/20001/src/IceTargetLowering.cpp
File src/IceTargetLowering.cpp (right):

https://codereview.chromium.org/870653002/diff/20001/src/IceTargetLowering.cp...
src/IceTargetLowering.cpp:107: Ctx->waitForWorkerThreads();
On 2015/01/22 20:50:56, JF wrote:
> It seems somewhat obscure to have emitConstants be the one that blocks and
waits
> for the worker threads. I'd instead have a higher level function which starts
> the threads, enqueues work, waits for the threads, and then emits constants
and
> others.

Looks like it should have already been done before this, so this one is
redundant?

   void ExitBlock() override {
     InstallGlobalNamesAndGlobalVarInitializers();
+    getTranslator().getContext()->waitForWorkerThreads();
     getTranslator().emitConstants();
   }

[Jim Stichnoth, 2015-01-23 07:55:55]

https://codereview.chromium.org/870653002/diff/20001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/870653002/diff/20001/src/IceCfg.cpp#newcode49
src/IceCfg.cpp:49: Cfg::~Cfg() { CurrentCfg = nullptr; }
On 2015/01/22 20:50:56, JF wrote:
> Comment that this is TLS.

Done.

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

https://codereview.chromium.org/870653002/diff/20001/src/IceGlobalContext.cpp...
src/IceGlobalContext.cpp:161: Func->dump();
On 2015/01/22 20:50:56, JF wrote:
> What are the above two for?

Documented.

https://codereview.chromium.org/870653002/diff/20001/src/IceGlobalContext.cpp...
src/IceGlobalContext.cpp:167: ErrorStatus = true;
On 2015/01/22 20:50:56, JF wrote:
> Should the thread continue when it has errors? Shouldn't the errors be in a
> container otherwise (so you know how many you received, and what they were)?

I do want to continue on an error, to give the user more information.  But I
don't know what to do beyond printing them and tracking whether the number of
errors is zero or nonzero (which is what's being done now).

https://codereview.chromium.org/870653002/diff/20001/src/IceGlobalContext.cpp...
src/IceGlobalContext.cpp:175: dumpStats(Func->getFunctionName());
On 2015/01/22 20:50:56, JF wrote:
> I think the stats should be joined at the end of the translation thread, and
> kept in TLS during translation.

Per-function stats should be dumped at this point, but you're right that
cumulative stats should be stored in TLS and joined at the end.  Added a TODO.

https://codereview.chromium.org/870653002/diff/20001/src/IceGlobalContext.cpp...
src/IceGlobalContext.cpp:177: delete Func;
On 2015/01/22 20:50:56, JF wrote:
> Could you use unique_ptr so that you don't need to delete manually?

There's already a TODO in IceCfg.h:33 about this.

https://codereview.chromium.org/870653002/diff/20001/src/IceGlobalContext.cpp...
src/IceGlobalContext.cpp:498: return;
On 2015/01/22 23:06:06, jvoung wrote:
> Could report_fatal_error for now?

Done.

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

https://codereview.chromium.org/870653002/diff/20001/src/IceGlobalContext.h#n...
src/IceGlobalContext.h:105: std::unique_lock<GlobalLockType> L(Lock);
On 2015/01/22 20:50:56, JF wrote:
> Can you add a comment on CfgQueue explaining the locking approach for the
> producer/consumer? I don't find this intuitive to read, even with the comments
> on the members below.

Done.
 
> I would also allow more Cfgs to be enqueued than there are workers: that's
what
> the PNaCl translator does because often functions are very small, so the
> consumers dequeue something like 10 functions at at time. This should be a
knob
> that we can tune later.

Renamed NumWorkers -> MaxSize, and added an explicit Sequential argument to the
ctor.  There can be knobs at a higher level to control it.

I can't imagine we would ever see any systematic difference from batching
dequeues in Subzero (though we might accidentally end up with a better load
balance), but we can certainly try.  Hopefully the batch would be based on total
bitcode size rather than number of functions.

https://codereview.chromium.org/870653002/diff/20001/src/IceGlobalContext.h#n...
src/IceGlobalContext.h:105: std::unique_lock<GlobalLockType> L(Lock);
On 2015/01/22 23:06:06, jvoung wrote:
> On 2015/01/22 20:50:56, JF wrote:
> > Can you add a comment on CfgQueue explaining the locking approach for the
> > producer/consumer? I don't find this intuitive to read, even with the
comments
> > on the members below.
> > 
> > I would also allow more Cfgs to be enqueued than there are workers: that's
> what
> > the PNaCl translator does because often functions are very small, so the
> > consumers dequeue something like 10 functions at at time. This should be a
> knob
> > that we can tune later.
> 
> 
> Yeah, for pnacl-llc, it dequeues N functions at a time, where the N starts at
> like 8 or 10, but the N tapers down to 1 near the end.

Even for small functions, my sense is that it takes a vast amount of time to
translate the function relative to the amount of time to lock and grab a work
item.  For my future benefit, do you happen to have a writeup of an analysis of
why chunking wins?

https://codereview.chromium.org/870653002/diff/20001/src/IceGlobalContext.h#n...
src/IceGlobalContext.h:141: std::queue<Cfg *> WorkQueue;
On 2015/01/22 20:50:56, JF wrote:
> This should probably be an std::array if the size is constant.

There is just one add() and one get() per function, so this seems really
unlikely to be contended.  The default queue<> in terms of deque<> seems like it
ought to have pretty good allocation performance, and I don't need to implement
a circular buffer for the push() and pop() operations.

https://codereview.chromium.org/870653002/diff/20001/src/IceGlobalContext.h#n...
src/IceGlobalContext.h:152: const uint32_t NumWorkers;
On 2015/01/22 20:50:56, JF wrote:
> I'd make this a size_t.

Done, here and in IceClFlags.h and llvm2ice.cpp.

https://codereview.chromium.org/870653002/diff/20001/src/IceGlobalContext.h#n...
src/IceGlobalContext.h:291: // just exit).
On 2015/01/22 20:50:56, JF wrote:
> "probably"? That seems mostly accurate.

Done.

https://codereview.chromium.org/870653002/diff/20001/src/IceGlobalContext.h#n...
src/IceGlobalContext.h:305: // TODO(stichnot): start emitter thread
On 2015/01/22 20:50:56, JF wrote:
> ?

Done.

https://codereview.chromium.org/870653002/diff/20001/src/IceGlobalContext.h#n...
src/IceGlobalContext.h:333: }
On 2015/01/22 20:50:56, JF wrote:
> I don't understand what this is for.

Hopefully documented better.

https://codereview.chromium.org/870653002/diff/20001/src/IceGlobalContext.h#n...
src/IceGlobalContext.h:364: bool ErrorStatus;
On 2015/01/22 20:50:56, JF wrote:
> Use std::error_code?

Done.

https://codereview.chromium.org/870653002/diff/20001/src/IceTargetLowering.cpp
File src/IceTargetLowering.cpp (right):

https://codereview.chromium.org/870653002/diff/20001/src/IceTargetLowering.cp...
src/IceTargetLowering.cpp:107: Ctx->waitForWorkerThreads();
On 2015/01/22 23:06:06, jvoung wrote:
> On 2015/01/22 20:50:56, JF wrote:
> > It seems somewhat obscure to have emitConstants be the one that blocks and
> waits
> > for the worker threads. I'd instead have a higher level function which
starts
> > the threads, enqueues work, waits for the threads, and then emits constants
> and
> > others.
> 
> Looks like it should have already been done before this, so this one is
> redundant?
> 
>    void ExitBlock() override {
>      InstallGlobalNamesAndGlobalVarInitializers();
> +    getTranslator().getContext()->waitForWorkerThreads();
>      getTranslator().emitConstants();
>    }

Done.

https://codereview.chromium.org/870653002/diff/20001/src/IceTargetLowering.cp...
src/IceTargetLowering.cpp:107: Ctx->waitForWorkerThreads();
On 2015/01/22 20:50:56, JF wrote:
> It seems somewhat obscure to have emitConstants be the one that blocks and
waits
> for the worker threads. I'd instead have a higher level function which starts
> the threads, enqueues work, waits for the threads, and then emits constants
and
> others.

Done, in main(), so that startWorkerThreads() and waitForWorkerThreads()
brackets the translation.

https://codereview.chromium.org/870653002/diff/20001/src/IceTargetLoweringX86...
File src/IceTargetLoweringX8632.h (right):

https://codereview.chromium.org/870653002/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.h:59: static void emitConstants(GlobalContext *Ctx);
On 2015/01/22 20:50:56, JF wrote:
> Why not keep this as override, and implement per target?
> 
> I wouldn't go the static route, I'd instead do static polymorphism through
> templates (which is easy to move towards from virtual functions).

The reason was explained in the CL description:

"TargetLowering::emitConstants() and related methods are changed to be static,
so that a valid TargetLowering object isn't required.  This is because the
TargetLowering object wants to hold a valid Cfg, and none really exists after
all functions are translated and the constant pool is ready for emission."

That is, emitConstants has nothing to do with a Cfg, and only needs to know the
GlobalContext in which the constant pool is stored.

Not sure why I didn't think of this before, but the existing
TargetGlobalInitLowering abstract class, and its target-specific concrete class,
is the perfect place for this.  I changed the name to TargetGlobalLowering to
reflect the more general functionality.

https://codereview.chromium.org/870653002/diff/20001/src/IceTranslator.h
File src/IceTranslator.h (left):

https://codereview.chromium.org/870653002/diff/20001/src/IceTranslator.h#oldc...
src/IceTranslator.h:86: std::unique_ptr<Cfg> Func;
On 2015/01/22 20:41:13, Karl wrote:
> Nice to see this wart go away!

Indeed.

https://codereview.chromium.org/870653002/diff/20001/src/llvm2ice.cpp
File src/llvm2ice.cpp (right):

https://codereview.chromium.org/870653002/diff/20001/src/llvm2ice.cpp#newcode209
src/llvm2ice.cpp:209: cl::init(0));
On 2015/01/22 20:50:56, JF wrote:
> This should default to std::thread::hardware_concurrency.
> 
> It's a bit confusing to have 0 and 1 be sequential, though 1 does generate a
> thread whereas 0 doesn't.

Well, 1 isn't exactly sequential, as there would be one translation thread in
addition to the parser thread and (eventually) the emitter thread.  0 means
everything is purely sequential with a single thread for everything, just as it
is pre-CL.

I added a comment to the code, but there's not much more space available in the
description string.

As for a std::thread::hardware_concurrency() default: maybe, or maybe that minus
2 to accommodate parser and emitter threads, or some browser max, or some
browser max minus 2, or some other resource balancing logic?  Added a TODO. :) 
For now, I'd keep it 0 to be minimally invasive while the dust settles (and
until I get tsan builds).  Later, at least 2 for recombobulation testing.

https://codereview.chromium.org/870653002/diff/20001/src/llvm2ice.cpp#newcode210
src/llvm2ice.cpp:210: static cl::alias SplitModule("split-module",
cl::desc("Alias for -threads"),
On 2015/01/22 20:50:56, JF wrote:
> On 2015/01/22 20:41:13, Karl wrote:
> > Not sure this can be an alias. Single threaded for pnacl-llc assume
> > split-module=1?
> 
> Why add the alias at all?

The idea was to make it easier to plumb llvm2ice alongside pnacl-llc in the
pnacl-translate script.  (Despite its misleading name.)

But OK OK I dropped it.

https://codereview.chromium.org/870653002/diff/20001/src/llvm2ice.cpp#newcode364
src/llvm2ice.cpp:364: int ErrorStatus = 0;
On 2015/01/22 20:50:56, JF wrote:
> This should also be an std::vector<std::error_code>.

Changed to std::error_code.

[JF, 2015-01-23 17:22:43]

Pre-meeting partial review.

https://codereview.chromium.org/870653002/diff/80001/src/IceGlobalContext.cpp
File src/IceGlobalContext.cpp (right):

https://codereview.chromium.org/870653002/diff/80001/src/IceGlobalContext.cpp...
src/IceGlobalContext.cpp:135: CfgQ(Flags.NumTranslationThreads,
(Flags.NumTranslationThreads == 0)),
Add /*MaxSize=*/ and /*Sequential=*/ here.

https://codereview.chromium.org/870653002/diff/80001/src/IceGlobalContext.h
File src/IceGlobalContext.h (right):

https://codereview.chromium.org/870653002/diff/80001/src/IceGlobalContext.h#n...
src/IceGlobalContext.h:170: bool IsEnded;
I think it's worth reordering and aligning to cacheline the members so they're
grouped as they're accessed most of the time (I'm thinking MOESI):
 - Written only by the producer but read by consumers (GrewOrEnded).
 - Written only by the consumers but read by producer (Shrunk).
 - Only be read by all (MaxSize/Sequential/IsEnded).
 - Read/write by all (Lock/WorkQueue).

This calls out how WorkQueue is used: it's probably better as a circular buffer,
where the front and back pointers are read/written exclusively by the
producer/consumer so they would be better positioned in different cachelines.
The buffer itself may end up aliasing when there's less work or when it gets too
full, but that's OK. I would really use a statically sized array for this, sized
to a power of 2, and use front/back with mod-of-a-constant-power-of-2 to find
elements.

Reordering as I suggest would make it perform better, but it also makes it way
easier to understand the design if the access patterns are explained properly.

https://codereview.chromium.org/870653002/diff/80001/src/IceTargetLowering.h
File src/IceTargetLowering.h (right):

https://codereview.chromium.org/870653002/diff/80001/src/IceTargetLowering.h#...
src/IceTargetLowering.h:251: TargetGlobalLowering &operator=(const
TargetGlobalLowering &) = delete;
TargetGlobalLowering() = delete;

[jvoung (off chromium), 2015-01-23 17:49:09]

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

https://codereview.chromium.org/870653002/diff/20001/src/IceGlobalContext.h#n...
src/IceGlobalContext.h:105: std::unique_lock<GlobalLockType> L(Lock);
On 2015/01/23 07:55:55, stichnot wrote:
> On 2015/01/22 23:06:06, jvoung wrote:
> > On 2015/01/22 20:50:56, JF wrote:
> > > Can you add a comment on CfgQueue explaining the locking approach for the
> > > producer/consumer? I don't find this intuitive to read, even with the
> comments
> > > on the members below.
> > > 
> > > I would also allow more Cfgs to be enqueued than there are workers: that's
> > what
> > > the PNaCl translator does because often functions are very small, so the
> > > consumers dequeue something like 10 functions at at time. This should be a
> > knob
> > > that we can tune later.
> > 
> > 
> > Yeah, for pnacl-llc, it dequeues N functions at a time, where the N starts
at
> > like 8 or 10, but the N tapers down to 1 near the end.
> 
> Even for small functions, my sense is that it takes a vast amount of time to
> translate the function relative to the amount of time to lock and grab a work
> item.  For my future benefit, do you happen to have a writeup of an analysis
of
> why chunking wins?


Sorry I don't have the numbers anymore, but it can be re-measured by tweaking
the knob under "RecommendedChunkSize()" in
tools/pnacl-llc/ThreadedFunctionQueue.h.

What I saw was that the synchronization added by dynamic scheduling w/ 1 dequeue
at a time was almost always worse that static scheduling by a few pct. It was
only after dequeuing more that the overhead was small enough to make dynamic
scheduling a win over static scheduling. Static scheduling didn't have any
synchronization though, since we were already duplicating bitcode reader state
and calculating function number % N == TID was all it took. There might have
been some other effects though -- I wasn't as careful about false-sharing and
cache lines.

In any case, there isn't static scheduling to compare against here, but it might
be worth measuring later.

The chunking + tapering method was just "Guided Self-Scheduling" which sehr
recommended.

[JF, 2015-01-23 17:51:02]

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

https://codereview.chromium.org/870653002/diff/20001/src/IceGlobalContext.h#n...
src/IceGlobalContext.h:105: std::unique_lock<GlobalLockType> L(Lock);
On 2015/01/23 17:49:09, jvoung wrote:
> On 2015/01/23 07:55:55, stichnot wrote:
> > On 2015/01/22 23:06:06, jvoung wrote:
> > > On 2015/01/22 20:50:56, JF wrote:
> > > > Can you add a comment on CfgQueue explaining the locking approach for
the
> > > > producer/consumer? I don't find this intuitive to read, even with the
> > comments
> > > > on the members below.
> > > > 
> > > > I would also allow more Cfgs to be enqueued than there are workers:
that's
> > > what
> > > > the PNaCl translator does because often functions are very small, so the
> > > > consumers dequeue something like 10 functions at at time. This should be
a
> > > knob
> > > > that we can tune later.
> > > 
> > > 
> > > Yeah, for pnacl-llc, it dequeues N functions at a time, where the N starts
> at
> > > like 8 or 10, but the N tapers down to 1 near the end.
> > 
> > Even for small functions, my sense is that it takes a vast amount of time to
> > translate the function relative to the amount of time to lock and grab a
work
> > item.  For my future benefit, do you happen to have a writeup of an analysis
> of
> > why chunking wins?
> 
> 
> Sorry I don't have the numbers anymore, but it can be re-measured by tweaking
> the knob under "RecommendedChunkSize()" in
> tools/pnacl-llc/ThreadedFunctionQueue.h.
> 
> What I saw was that the synchronization added by dynamic scheduling w/ 1
dequeue
> at a time was almost always worse that static scheduling by a few pct. It was
> only after dequeuing more that the overhead was small enough to make dynamic
> scheduling a win over static scheduling. Static scheduling didn't have any
> synchronization though, since we were already duplicating bitcode reader state
> and calculating function number % N == TID was all it took. There might have
> been some other effects though -- I wasn't as careful about false-sharing and
> cache lines.
> 
> In any case, there isn't static scheduling to compare against here, but it
might
> be worth measuring later.
> 
> The chunking + tapering method was just "Guided Self-Scheduling" which sehr
> recommended.

Code review was:
  https://codereview.chromium.org/196793026/

[Jim Stichnoth, 2015-01-23 21:54:02]

https://codereview.chromium.org/870653002/diff/80001/src/IceGlobalContext.cpp
File src/IceGlobalContext.cpp (right):

https://codereview.chromium.org/870653002/diff/80001/src/IceGlobalContext.cpp...
src/IceGlobalContext.cpp:135: CfgQ(Flags.NumTranslationThreads,
(Flags.NumTranslationThreads == 0)),
On 2015/01/23 17:22:43, JF wrote:
> Add /*MaxSize=*/ and /*Sequential=*/ here.

Nice, done.

https://codereview.chromium.org/870653002/diff/80001/src/IceGlobalContext.h
File src/IceGlobalContext.h (right):

https://codereview.chromium.org/870653002/diff/80001/src/IceGlobalContext.h#n...
src/IceGlobalContext.h:170: bool IsEnded;
On 2015/01/23 17:22:43, JF wrote:
> I think it's worth reordering and aligning to cacheline the members so they're
> grouped as they're accessed most of the time (I'm thinking MOESI):
>  - Written only by the producer but read by consumers (GrewOrEnded).
>  - Written only by the consumers but read by producer (Shrunk).
>  - Only be read by all (MaxSize/Sequential/IsEnded).
>  - Read/write by all (Lock/WorkQueue).
> 
> This calls out how WorkQueue is used: it's probably better as a circular
buffer,
> where the front and back pointers are read/written exclusively by the
> producer/consumer so they would be better positioned in different cachelines.
> The buffer itself may end up aliasing when there's less work or when it gets
too
> full, but that's OK. I would really use a statically sized array for this,
sized
> to a power of 2, and use front/back with mod-of-a-constant-power-of-2 to find
> elements.
> 
> Reordering as I suggest would make it perform better, but it also makes it way
> easier to understand the design if the access patterns are explained properly.

Done.  And added a TODO about considering std::array for a circular buffer.

https://codereview.chromium.org/870653002/diff/80001/src/IceTargetLowering.h
File src/IceTargetLowering.h (right):

https://codereview.chromium.org/870653002/diff/80001/src/IceTargetLowering.h#...
src/IceTargetLowering.h:251: TargetGlobalLowering &operator=(const
TargetGlobalLowering &) = delete;
On 2015/01/23 17:22:43, JF wrote:
> TargetGlobalLowering() = delete;

Done.  (also for TargetGlobalX8632)

[JF, 2015-01-23 22:22:11]

https://codereview.chromium.org/870653002/diff/100001/src/IceGlobalContext.h
File src/IceGlobalContext.h (right):

https://codereview.chromium.org/870653002/diff/100001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:167: alignas(MaxCacheLineSize) bool IsEnded;
Move to end with Sequential: it's only written to once, during normal operation
it's only read.

[jvoung (off chromium), 2015-01-23 22:56:37]

https://codereview.chromium.org/870653002/diff/100001/src/IceTranslator.h
File src/IceTranslator.h (right):

https://codereview.chromium.org/870653002/diff/100001/src/IceTranslator.h#new...
src/IceTranslator.h:71: // the exit status of the translation. False is
successful. True
Back to "The"?

https://codereview.chromium.org/870653002/diff/100001/src/llvm2ice.cpp
File src/llvm2ice.cpp (right):

https://codereview.chromium.org/870653002/diff/100001/src/llvm2ice.cpp#newcod...
src/llvm2ice.cpp:401: // Error status is the combination of the bitcode parser's
error
Seems like this could be a bit confusing but "translation error status" I'm
thinking is from each Func, yet it's stored in Ctx. On the other hand "bitcode
parser's error" is from Translator->getErrorStatus()?

Though shared between threads, would it make sense to set it in the context or
one place always?

[JF, 2015-01-23 23:01:47]

https://codereview.chromium.org/870653002/diff/100001/src/IceGlobalContext.h
File src/IceGlobalContext.h (right):

https://codereview.chromium.org/870653002/diff/100001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:110: // which the single thread should never wait().
Shouldn't the locks be entirely bypassed when sequential? That would make the
non-sequential code easier to read, and you'd probably have sequential and
non-sequential tsan tests.

https://codereview.chromium.org/870653002/diff/100001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:119: : IsEnded(false), MaxSize(MaxSize),
Sequential(Sequential) {}
Should the CfgQueue assert that the queue is empty (I guess it would need to
grab the lock for this to work)? It seems unlikely to get messed up, but it
would be tricky to find if it is!

[Jim Stichnoth, 2015-01-25 07:29:39]

https://codereview.chromium.org/870653002/diff/100001/src/IceGlobalContext.h
File src/IceGlobalContext.h (right):

https://codereview.chromium.org/870653002/diff/100001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:110: // which the single thread should never wait().
On 2015/01/23 23:01:47, JF wrote:
> Shouldn't the locks be entirely bypassed when sequential? That would make the
> non-sequential code easier to read, and you'd probably have sequential and
> non-sequential tsan tests.

Nice, done.

https://codereview.chromium.org/870653002/diff/100001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:119: : IsEnded(false), MaxSize(MaxSize),
Sequential(Sequential) {}
On 2015/01/23 23:01:47, JF wrote:
> Should the CfgQueue assert that the queue is empty (I guess it would need to
> grab the lock for this to work)? It seems unlikely to get messed up, but it
> would be tricky to find if it is!

I don't see how the WorkQueue could ever be non-empty in the CfgQueue ctor?

https://codereview.chromium.org/870653002/diff/100001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:167: alignas(MaxCacheLineSize) bool IsEnded;
On 2015/01/23 22:22:11, JF wrote:
> Move to end with Sequential: it's only written to once, during normal
operation
> it's only read.

Done.

https://codereview.chromium.org/870653002/diff/100001/src/IceTranslator.h
File src/IceTranslator.h (right):

https://codereview.chromium.org/870653002/diff/100001/src/IceTranslator.h#new...
src/IceTranslator.h:71: // the exit status of the translation. False is
successful. True
On 2015/01/23 22:56:37, jvoung wrote:
> Back to "The"?

Done.

https://codereview.chromium.org/870653002/diff/100001/src/llvm2ice.cpp
File src/llvm2ice.cpp (right):

https://codereview.chromium.org/870653002/diff/100001/src/llvm2ice.cpp#newcod...
src/llvm2ice.cpp:401: // Error status is the combination of the bitcode parser's
error
On 2015/01/23 22:56:37, jvoung wrote:
> Seems like this could be a bit confusing but "translation error status" I'm
> thinking is from each Func, yet it's stored in Ctx. On the other hand "bitcode
> parser's error" is from Translator->getErrorStatus()?
> 
> Though shared between threads, would it make sense to set it in the context or
> one place always?

Good point.  Originally, each function tracked its own error status and then on
error, copied it into the GlobalContext.  (This happened to be locked by the
Ostream locker, but I just changed it to use its own lock.)  Separately, the
Translator tracks its own parsing error state.

I think it's good for the translator to continue tracking its own state, but I
added a step to merge the translator's error state with GlobalContext at the
end, simplifying the code here.

[Jim Stichnoth, 2015-01-25 21:25:31]

Added a TSAN=1 option to Makefile.standalone to enable ThreadSanitizer.

I had to deliberately remove a lock to test that tsan was actually working
correctly. :)

[JF, 2015-01-25 22:57:01]

OK I took a look at the difficult part of the code. I think we're getting close,
I'm just not comfortable with the IsEnded part.

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.cpp
File src/IceGlobalContext.cpp (right):

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.cp...
src/IceGlobalContext.cpp:174: getErrorStatus()->assign(1,
std::generic_category());
Make the error numbers an enum, and use std::is_error_condition_enum. I think
it's better for you to make your own class that derives from
std::error_category.

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h
File src/IceGlobalContext.h (right):

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:120: class CfgQueue {
It's probably better to put this class in its own header, and call it:
template<typename T> class BoundedProducerConsumerQueue;

Where T is Cfg* for the one use you have. That will make it easier to write unit
tests if you're into that, and benchmark other implementations if/when we get
there and it makes sense.

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:123: : MaxSize(MaxSize), Sequential(Sequential),
IsEnded(false) {}
WorkQueue.reserve(MaxSize)

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:124: void add(Cfg *Func) {
I'd rename to blocking_push or something similar, so the code calling this makes
the blocking behavior obvious.

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:134: }
This code:
  while (WorkQueue.size() >= MaxSize) {
    Shrunk.wait(L);
  }
Could instead be:
  Shrunk.wait(L, [this]{return WorkQueue.size() < MaxSize;});

This makes the spurious wake-up handling easier to understand IMO (and more
C++11-idiomatic).

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:139: Cfg *get() {
I'd rename to wait_and_pop or something similar.

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:149: while (!IsEnded || !WorkQueue.empty()) {
Similarly here, I'd go with:

Cfg *wait_and_pop() {
  if (Sequential) {
    ...
  }
  std::unique_lock<GlobalLockType> L(lock);
  GrewOrEnded.wait(L, [this]{return IsEnded || !WorkQueue.empty();});
  if (IsEnded)
    return nullptr;
  Cfg *Func = WorkQueue.front();
  WorkQueue.pop();
  L.unlock();
  Shrunk.notify_one();
  return Func;
}

Actually, I'm not sure this rewrite is entirely correct: the wait condition is,
but the handling of IsEnded is different. Am I misunderstanding how you want to
handle IsEnded? The code could continue looking at !WorkQueue.empty(), but it
seems like once work ends you're waking up all threads with notify_all() and
they may have nothing to do, so they'll { wakeup/go to sleep } in a loop?

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:166: L.unlock();
Could you just use a lock_guard and scoping here?

void end() {
  if (Sequential)
    return;
  {
    std::lock_guard<GlobalLockType> L(Lock);
    IsEnded = true;
  }
  GrewOrEnded.notify_all();
}

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:170: private:
CfGQueue() = delete;
CfgQueue(const CfgQueue &) = delete;

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:412: const VerboseMask VMask;
alignas after the streams.

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:418: RandomNumberGenerator RNG;
Add a TODO to move the out of this class.

[Jim Stichnoth, 2015-01-26 04:59:44]

error_code comment still to be addressed.

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h
File src/IceGlobalContext.h (right):

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:120: class CfgQueue {
On 2015/01/25 22:57:00, JF wrote:
> It's probably better to put this class in its own header, and call it:
> template<typename T> class BoundedProducerConsumerQueue;
> 
> Where T is Cfg* for the one use you have. That will make it easier to write
unit
> tests if you're into that, and benchmark other implementations if/when we get
> there and it makes sense.

Done.

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:123: : MaxSize(MaxSize), Sequential(Sequential),
IsEnded(false) {}
On 2015/01/25 22:57:00, JF wrote:
> WorkQueue.reserve(MaxSize)

There's no std::queue::reserve() or std::deque::reserve().  But that's a good
idea to add to a comment when std::queue gets replaced by vector or array.

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:124: void add(Cfg *Func) {
On 2015/01/25 22:57:00, JF wrote:
> I'd rename to blocking_push or something similar, so the code calling this
makes
> the blocking behavior obvious.

Done.  add() --> blockingPush(), and get() --> blockingPop().

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:134: }
On 2015/01/25 22:57:00, JF wrote:
> This code:
>   while (WorkQueue.size() >= MaxSize) {
>     Shrunk.wait(L);
>   }
> Could instead be:
>   Shrunk.wait(L, [this]{return WorkQueue.size() < MaxSize;});
> 
> This makes the spurious wake-up handling easier to understand IMO (and more
> C++11-idiomatic).

Wow.  Done.
(my first ever C++ lambda)

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:139: Cfg *get() {
On 2015/01/25 22:57:00, JF wrote:
> I'd rename to wait_and_pop or something similar.

Done.

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:149: while (!IsEnded || !WorkQueue.empty()) {
On 2015/01/25 22:57:00, JF wrote:
> Similarly here, I'd go with:
> 
> Cfg *wait_and_pop() {
>   if (Sequential) {
>     ...
>   }
>   std::unique_lock<GlobalLockType> L(lock);
>   GrewOrEnded.wait(L, [this]{return IsEnded || !WorkQueue.empty();});
>   if (IsEnded)
>     return nullptr;
>   Cfg *Func = WorkQueue.front();
>   WorkQueue.pop();
>   L.unlock();
>   Shrunk.notify_one();
>   return Func;
> }
> 
> Actually, I'm not sure this rewrite is entirely correct: the wait condition
is,
> but the handling of IsEnded is different. Am I misunderstanding how you want
to
> handle IsEnded? The code could continue looking at !WorkQueue.empty(), but it
> seems like once work ends you're waking up all threads with notify_all() and
> they may have nothing to do, so they'll { wakeup/go to sleep } in a loop?

Yeah, your rewrite could have the workers shut down while there are still items
on the queue to be processed, just because the producer finished creating work. 
I clarified in the comment outside of the class, that nullptr is never returned
if there were still items on the queue.

So, after these rewrites, the if(Sequential) code is disturbingly similar to the
parallel code.  Time to merge them?  (despite the slightly less efficient
execution in the sequential case which wouldn't actually be deployed)

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:166: L.unlock();
On 2015/01/25 22:57:00, JF wrote:
> Could you just use a lock_guard and scoping here?
> 
> void end() {
>   if (Sequential)
>     return;
>   {
>     std::lock_guard<GlobalLockType> L(Lock);
>     IsEnded = true;
>   }
>   GrewOrEnded.notify_all();
> }

I thought about this for all 3 methods, but since the get() method (at least as
currently written) couldn't be done that way, I went with consistency.

But thinking about it more, the .unlock() optimization just adds clutter so I'll
go with your suggestion and minimize them.

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:170: private:
On 2015/01/25 22:57:00, JF wrote:
> CfGQueue() = delete;
> CfgQueue(const CfgQueue &) = delete;

<shamecube> Done.

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:412: const VerboseMask VMask;
On 2015/01/25 22:57:00, JF wrote:
> alignas after the streams.

Done.  (wish it was easier to add these boundaries...)

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:418: RandomNumberGenerator RNG;
On 2015/01/25 22:57:00, JF wrote:
> Add a TODO to move the out of this class.

Done.

[JF, 2015-01-26 17:54:51]

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h
File src/IceGlobalContext.h (right):

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:123: : MaxSize(MaxSize), Sequential(Sequential),
IsEnded(false) {}
On 2015/01/26 04:59:43, stichnot wrote:
> On 2015/01/25 22:57:00, JF wrote:
> > WorkQueue.reserve(MaxSize)
> 
> There's no std::queue::reserve() or std::deque::reserve().  But that's a good
> idea to add to a comment when std::queue gets replaced by vector or array.

:(

I'm still not a fan of using queue, the default container backing it is a deque
so every push/pop will move elements around, and can allocate, all of that while
you're holding a lock. I'd rather have a bounded container in this CL.

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:149: while (!IsEnded || !WorkQueue.empty()) {
On 2015/01/26 04:59:43, stichnot wrote:
> On 2015/01/25 22:57:00, JF wrote:
> > Similarly here, I'd go with:
> > 
> > Cfg *wait_and_pop() {
> >   if (Sequential) {
> >     ...
> >   }
> >   std::unique_lock<GlobalLockType> L(lock);
> >   GrewOrEnded.wait(L, [this]{return IsEnded || !WorkQueue.empty();});
> >   if (IsEnded)
> >     return nullptr;
> >   Cfg *Func = WorkQueue.front();
> >   WorkQueue.pop();
> >   L.unlock();
> >   Shrunk.notify_one();
> >   return Func;
> > }
> > 
> > Actually, I'm not sure this rewrite is entirely correct: the wait condition
> is,
> > but the handling of IsEnded is different. Am I misunderstanding how you want
> to
> > handle IsEnded? The code could continue looking at !WorkQueue.empty(), but
it
> > seems like once work ends you're waking up all threads with notify_all() and
> > they may have nothing to do, so they'll { wakeup/go to sleep } in a loop?
> 
> Yeah, your rewrite could have the workers shut down while there are still
items
> on the queue to be processed, just because the producer finished creating
work. 
> I clarified in the comment outside of the class, that nullptr is never
returned
> if there were still items on the queue.
> 
> So, after these rewrites, the if(Sequential) code is disturbingly similar to
the
> parallel code.  Time to merge them?  (despite the slightly less efficient
> execution in the sequential case which wouldn't actually be deployed)

I'm in for killing Sequential, it'll make the non-sequential code faster.

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:412: const VerboseMask VMask;
On 2015/01/26 04:59:44, stichnot wrote:
> On 2015/01/25 22:57:00, JF wrote:
> > alignas after the streams.
> 
> Done.  (wish it was easier to add these boundaries...)

Your wish is my command:

#define ICE_CACHELINE_BOUNDARY __attribute__((aligned(MacCacheLineSize))) int :
0

*WARNING* this isn't standard. You can't use alignas here because bitfields
can't have alignas, but IMHO this restriction should be lifted from the standard
in the case of zero-width bitfields. I'll try to get this into the next standard
;-)

https://codereview.chromium.org/870653002/diff/200001/src/IceGlobalContext.h
File src/IceGlobalContext.h (right):

https://codereview.chromium.org/870653002/diff/200001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:237: Cfg *cfgQueueGet() { return CfgQ.blockingPop(); }
I'd change these names too (add/get to blockingPush/bloxkingPop).

https://codereview.chromium.org/870653002/diff/200001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:239: void cfgQueueEnd() { CfgQ.end(); }
Now that I think of it, notifyEnded would probably be clearer.

https://codereview.chromium.org/870653002/diff/200001/src/IceUtils.h
File src/IceUtils.h (right):

https://codereview.chromium.org/870653002/diff/200001/src/IceUtils.h#newcode87
src/IceUtils.h:87: // supports it.
TODO

[JF, 2015-01-26 18:05:26]

https://codereview.chromium.org/870653002/diff/200001/src/IceUtils.h
File src/IceUtils.h (right):

https://codereview.chromium.org/870653002/diff/200001/src/IceUtils.h#newcode121
src/IceUtils.h:121: return Func;
How about this:

T *Func = nullptr;
bool ShouldNotifyProducer = false;
{
  std::unique_lock<GlobalLockType> L(Lock);
  GrewOrEnded.wait(L, [this] { return IsEnded || !WorkQueue.empty(); });
  if (!WorkQueue.empty()) {
    Func = WorkQueue.front();
    WorkQueue.pop();
    ShouldNotifyProducer = !IsEnded;
  }
}
if (ShouldNotifyProducer)
  Shrunk.notify_one();
return Func;

[JF, 2015-01-26 18:10:40]

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h
File src/IceGlobalContext.h (right):

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:166: L.unlock();
On 2015/01/26 04:59:43, stichnot wrote:
> On 2015/01/25 22:57:00, JF wrote:
> > Could you just use a lock_guard and scoping here?
> > 
> > void end() {
> >   if (Sequential)
> >     return;
> >   {
> >     std::lock_guard<GlobalLockType> L(Lock);
> >     IsEnded = true;
> >   }
> >   GrewOrEnded.notify_all();
> > }
> 
> I thought about this for all 3 methods, but since the get() method (at least
as
> currently written) couldn't be done that way, I went with consistency.
> 
> But thinking about it more, the .unlock() optimization just adds clutter so
I'll
> go with your suggestion and minimize them.

As discussed offline, lock_guard is simpler than unique_lock so it'll generate
better code (in theory the compiler could emit the same code for unique_lock
used as a lock_guard, but I wouldn't count on it). You're not passing the lock
to a condvar in this method, so it's the only place where you could avoid
unique_lock.

[JF, 2015-01-26 19:11:49]

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h
File src/IceGlobalContext.h (right):

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:412: const VerboseMask VMask;
On 2015/01/26 17:54:50, JF wrote:
> On 2015/01/26 04:59:44, stichnot wrote:
> > On 2015/01/25 22:57:00, JF wrote:
> > > alignas after the streams.
> > 
> > Done.  (wish it was easier to add these boundaries...)
> 
> Your wish is my command:
> 
> #define ICE_CACHELINE_BOUNDARY __attribute__((aligned(MacCacheLineSize))) int
:
> 0
> 
> *WARNING* this isn't standard. You can't use alignas here because bitfields
> can't have alignas, but IMHO this restriction should be lifted from the
standard
> in the case of zero-width bitfields. I'll try to get this into the next
standard
> ;-)

A standard-compliant solution pointed out by Richard Smith:

alignas(MaxCacheLineSize) struct {};

[Karl, 2015-01-26 22:53:47]

https://codereview.chromium.org/870653002/diff/200001/src/PNaClTranslator.cpp
File src/PNaClTranslator.cpp (right):

https://codereview.chromium.org/870653002/diff/200001/src/PNaClTranslator.cpp...
src/PNaClTranslator.cpp:363: std::error_code &ErrorStatus;
As per our earlier discussion, This should be flexible enough to allow error
recovery (and hence potentially multiple errors with user-useful feedback), and
to report the first error as the summary (since it is the most likely to be
correct).

[Jim Stichnoth, 2015-01-27 00:56:18]

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.cpp
File src/IceGlobalContext.cpp (right):

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.cp...
src/IceGlobalContext.cpp:174: getErrorStatus()->assign(1,
std::generic_category());
On 2015/01/25 22:57:00, JF wrote:
> Make the error numbers an enum, and use std::is_error_condition_enum. I think
> it's better for you to make your own class that derives from
> std::error_category.

Created the Ice::ErrorCode class and used it where appropriate.

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h
File src/IceGlobalContext.h (right):

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:123: : MaxSize(MaxSize), Sequential(Sequential),
IsEnded(false) {}
On 2015/01/26 17:54:50, JF wrote:
> On 2015/01/26 04:59:43, stichnot wrote:
> > On 2015/01/25 22:57:00, JF wrote:
> > > WorkQueue.reserve(MaxSize)
> > 
> > There's no std::queue::reserve() or std::deque::reserve().  But that's a
good
> > idea to add to a comment when std::queue gets replaced by vector or array.
> 
> :(
> 
> I'm still not a fan of using queue, the default container backing it is a
deque
> so every push/pop will move elements around, and can allocate, all of that
while
> you're holding a lock. I'd rather have a bounded container in this CL.

Done.

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:149: while (!IsEnded || !WorkQueue.empty()) {
On 2015/01/26 17:54:50, JF wrote:
> On 2015/01/26 04:59:43, stichnot wrote:
> > On 2015/01/25 22:57:00, JF wrote:
> > > Similarly here, I'd go with:
> > > 
> > > Cfg *wait_and_pop() {
> > >   if (Sequential) {
> > >     ...
> > >   }
> > >   std::unique_lock<GlobalLockType> L(lock);
> > >   GrewOrEnded.wait(L, [this]{return IsEnded || !WorkQueue.empty();});
> > >   if (IsEnded)
> > >     return nullptr;
> > >   Cfg *Func = WorkQueue.front();
> > >   WorkQueue.pop();
> > >   L.unlock();
> > >   Shrunk.notify_one();
> > >   return Func;
> > > }
> > > 
> > > Actually, I'm not sure this rewrite is entirely correct: the wait
condition
> > is,
> > > but the handling of IsEnded is different. Am I misunderstanding how you
want
> > to
> > > handle IsEnded? The code could continue looking at !WorkQueue.empty(), but
> it
> > > seems like once work ends you're waking up all threads with notify_all()
and
> > > they may have nothing to do, so they'll { wakeup/go to sleep } in a loop?
> > 
> > Yeah, your rewrite could have the workers shut down while there are still
> items
> > on the queue to be processed, just because the producer finished creating
> work. 
> > I clarified in the comment outside of the class, that nullptr is never
> returned
> > if there were still items on the queue.
> > 
> > So, after these rewrites, the if(Sequential) code is disturbingly similar to
> the
> > parallel code.  Time to merge them?  (despite the slightly less efficient
> > execution in the sequential case which wouldn't actually be deployed)
> 
> I'm in for killing Sequential, it'll make the non-sequential code faster.

Done.

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:166: L.unlock();
On 2015/01/26 18:10:40, JF wrote:
> On 2015/01/26 04:59:43, stichnot wrote:
> > On 2015/01/25 22:57:00, JF wrote:
> > > Could you just use a lock_guard and scoping here?
> > > 
> > > void end() {
> > >   if (Sequential)
> > >     return;
> > >   {
> > >     std::lock_guard<GlobalLockType> L(Lock);
> > >     IsEnded = true;
> > >   }
> > >   GrewOrEnded.notify_all();
> > > }
> > 
> > I thought about this for all 3 methods, but since the get() method (at least
> as
> > currently written) couldn't be done that way, I went with consistency.
> > 
> > But thinking about it more, the .unlock() optimization just adds clutter so
> I'll
> > go with your suggestion and minimize them.
> 
> As discussed offline, lock_guard is simpler than unique_lock so it'll generate
> better code (in theory the compiler could emit the same code for unique_lock
> used as a lock_guard, but I wouldn't count on it). You're not passing the lock
> to a condvar in this method, so it's the only place where you could avoid
> unique_lock.

Done.

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:412: const VerboseMask VMask;
On 2015/01/26 17:54:50, JF wrote:
> On 2015/01/26 04:59:44, stichnot wrote:
> > On 2015/01/25 22:57:00, JF wrote:
> > > alignas after the streams.
> > 
> > Done.  (wish it was easier to add these boundaries...)
> 
> Your wish is my command:
> 
> #define ICE_CACHELINE_BOUNDARY __attribute__((aligned(MacCacheLineSize))) int
:
> 0
> 
> *WARNING* this isn't standard. You can't use alignas here because bitfields
> can't have alignas, but IMHO this restriction should be lifted from the
standard
> in the case of zero-width bitfields. I'll try to get this into the next
standard
> ;-)

Cool, thanks!

https://codereview.chromium.org/870653002/diff/140001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:412: const VerboseMask VMask;
On 2015/01/26 19:11:48, JF wrote:
> On 2015/01/26 17:54:50, JF wrote:
> > On 2015/01/26 04:59:44, stichnot wrote:
> > > On 2015/01/25 22:57:00, JF wrote:
> > > > alignas after the streams.
> > > 
> > > Done.  (wish it was easier to add these boundaries...)
> > 
> > Your wish is my command:
> > 
> > #define ICE_CACHELINE_BOUNDARY __attribute__((aligned(MacCacheLineSize)))
int
> :
> > 0
> > 
> > *WARNING* this isn't standard. You can't use alignas here because bitfields
> > can't have alignas, but IMHO this restriction should be lifted from the
> standard
> > in the case of zero-width bitfields. I'll try to get this into the next
> standard
> > ;-)
> 
> A standard-compliant solution pointed out by Richard Smith:
> 
> alignas(MaxCacheLineSize) struct {};

Done.

https://codereview.chromium.org/870653002/diff/200001/src/IceGlobalContext.h
File src/IceGlobalContext.h (right):

https://codereview.chromium.org/870653002/diff/200001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:237: Cfg *cfgQueueGet() { return CfgQ.blockingPop(); }
On 2015/01/26 17:54:50, JF wrote:
> I'd change these names too (add/get to blockingPush/bloxkingPop).

Done.

https://codereview.chromium.org/870653002/diff/200001/src/IceGlobalContext.h#...
src/IceGlobalContext.h:239: void cfgQueueEnd() { CfgQ.end(); }
On 2015/01/26 17:54:51, JF wrote:
> Now that I think of it, notifyEnded would probably be clearer.

Done.

https://codereview.chromium.org/870653002/diff/200001/src/IceUtils.h
File src/IceUtils.h (right):

https://codereview.chromium.org/870653002/diff/200001/src/IceUtils.h#newcode87
src/IceUtils.h:87: // supports it.
On 2015/01/26 17:54:51, JF wrote:
> TODO

Implemented a circular buffer instead.

https://codereview.chromium.org/870653002/diff/200001/src/IceUtils.h#newcode121
src/IceUtils.h:121: return Func;
On 2015/01/26 18:05:26, JF wrote:
> How about this:
> 
> T *Func = nullptr;
> bool ShouldNotifyProducer = false;
> {
>   std::unique_lock<GlobalLockType> L(Lock);
>   GrewOrEnded.wait(L, [this] { return IsEnded || !WorkQueue.empty(); });
>   if (!WorkQueue.empty()) {
>     Func = WorkQueue.front();
>     WorkQueue.pop();
>     ShouldNotifyProducer = !IsEnded;
>   }
> }
> if (ShouldNotifyProducer)
>   Shrunk.notify_one();
> return Func;

Done.

https://codereview.chromium.org/870653002/diff/200001/src/PNaClTranslator.cpp
File src/PNaClTranslator.cpp (right):

https://codereview.chromium.org/870653002/diff/200001/src/PNaClTranslator.cpp...
src/PNaClTranslator.cpp:363: std::error_code &ErrorStatus;
On 2015/01/26 22:53:47, Karl wrote:
> As per our earlier discussion, This should be flexible enough to allow error
> recovery (and hence potentially multiple errors with user-useful feedback),
and
> to report the first error as the summary (since it is the most likely to be
> correct).

See the new ErrorCode class, which prefers the first error given to it.

[JF, 2015-01-27 01:53:34]

A few nits, then LGTM ლ(╹◡╹ლ)

https://codereview.chromium.org/870653002/diff/220001/src/IceDefs.h
File src/IceDefs.h (right):

https://codereview.chromium.org/870653002/diff/220001/src/IceDefs.h#newcode205
src/IceDefs.h:205: ErrorCode() : std::error_code(), HasError(false) {}
Calling the std::error_code ctor here doesn't seem necessary.

https://codereview.chromium.org/870653002/diff/220001/src/IceUtils.h
File src/IceUtils.h (right):

https://codereview.chromium.org/870653002/diff/220001/src/IceUtils.h#newcode58
src/IceUtils.h:58: // producers and multiple consumers.  The producer adds
entries using
You should probably pluralize "producer" everywhere, since there's no Highlander
assumption (that there can only be one).

https://codereview.chromium.org/870653002/diff/220001/src/IceUtils.h#newcode146
src/IceUtils.h:146: // be pushed.
Written by the producer.

https://codereview.chromium.org/870653002/diff/220001/src/IceUtils.h#newcode156
src/IceUtils.h:156: // i.e. the next to be popped.
Written by the consumer.

https://codereview.chromium.org/870653002/diff/220001/src/IceUtils.h#newcode170
src/IceUtils.h:170: size_t size() const { return (Back - Front) &
MaxStaticSizeMask; }
It took me a moment to convince myself that this was correct when Back=0 and
Front=127 (there's a single element, at the very end of the array, and the next
insertion point is at the very front). That case does indeed return 1 as the
size.

No action needed, just saying I stared and squinted.

[Jim Stichnoth, 2015-01-27 05:35:12]

https://codereview.chromium.org/870653002/diff/220001/src/IceDefs.h
File src/IceDefs.h (right):

https://codereview.chromium.org/870653002/diff/220001/src/IceDefs.h#newcode205
src/IceDefs.h:205: ErrorCode() : std::error_code(), HasError(false) {}
On 2015/01/27 01:53:33, JF wrote:
> Calling the std::error_code ctor here doesn't seem necessary.

Right - I was just trying to make it clear that the no-arg parent ctor was being
used, but I'm happy to remove it.

https://codereview.chromium.org/870653002/diff/220001/src/IceUtils.h
File src/IceUtils.h (right):

https://codereview.chromium.org/870653002/diff/220001/src/IceUtils.h#newcode58
src/IceUtils.h:58: // producers and multiple consumers.  The producer adds
entries using
On 2015/01/27 01:53:34, JF wrote:
> You should probably pluralize "producer" everywhere, since there's no
Highlander
> assumption (that there can only be one).

Changed to "a producer" / "a consumer".

https://codereview.chromium.org/870653002/diff/220001/src/IceUtils.h#newcode146
src/IceUtils.h:146: // be pushed.
On 2015/01/27 01:53:33, JF wrote:
> Written by the producer.

Done.

https://codereview.chromium.org/870653002/diff/220001/src/IceUtils.h#newcode156
src/IceUtils.h:156: // i.e. the next to be popped.
On 2015/01/27 01:53:33, JF wrote:
> Written by the consumer.

Done.

https://codereview.chromium.org/870653002/diff/220001/src/IceUtils.h#newcode170
src/IceUtils.h:170: size_t size() const { return (Back - Front) &
MaxStaticSizeMask; }
On 2015/01/27 01:53:34, JF wrote:
> It took me a moment to convince myself that this was correct when Back=0 and
> Front=127 (there's a single element, at the very end of the array, and the
next
> insertion point is at the very front). That case does indeed return 1 as the
> size.
> 
> No action needed, just saying I stared and squinted.

Me too, because it's too simple, right?

Actually, it just occurred to me that push() could do a simple Back++ and pop
could do a simple Front++, then size() would be a simple Back-Front and
WorkItems[i] would change to WorkItems[i&MaxStaticSizeMask].  This would allow
MaxSize to be as high as MaxStaticSize, instead of MaxStaticSize-1.  Maybe
that's what you meant in the first place?

The implementation is a bit more compact, so I went ahead with it.  I tested by
changing most of the size_t to uint8_t to make sure Front/Back would wrap.

[JF, 2015-01-27 06:04:36]

Mucho mas LGTM.

https://codereview.chromium.org/870653002/diff/220001/src/IceUtils.h
File src/IceUtils.h (right):

https://codereview.chromium.org/870653002/diff/220001/src/IceUtils.h#newcode170
src/IceUtils.h:170: size_t size() const { return (Back - Front) &
MaxStaticSizeMask; }
On 2015/01/27 05:35:11, stichnot wrote:
> On 2015/01/27 01:53:34, JF wrote:
> > It took me a moment to convince myself that this was correct when Back=0 and
> > Front=127 (there's a single element, at the very end of the array, and the
> next
> > insertion point is at the very front). That case does indeed return 1 as the
> > size.
> > 
> > No action needed, just saying I stared and squinted.
> 
> Me too, because it's too simple, right?
> 
> Actually, it just occurred to me that push() could do a simple Back++ and pop
> could do a simple Front++, then size() would be a simple Back-Front and
> WorkItems[i] would change to WorkItems[i&MaxStaticSizeMask].  This would allow
> MaxSize to be as high as MaxStaticSize, instead of MaxStaticSize-1.  Maybe
> that's what you meant in the first place?
> 
> The implementation is a bit more compact, so I went ahead with it.  I tested
by
> changing most of the size_t to uint8_t to make sure Front/Back would wrap.

Oh yeah that's way better!

[Jim Stichnoth, 2015-01-27 13:06:07]

Committed patchset #14 (id:260001) manually as
fa4efea5413aa993e8e6ba10579e0934d1a3e784 (presubmit successful).