On Wednesday 27 October 2010 05:14, Rob Landley wrote:
> On Tuesday 26 October 2010 16:26:39 Denys Vlasenko wrote:
> > On Tuesday 26 October 2010 19:36, Rob Landley wrote:
> > > > The only piece of software of the 1024 CPU machine which
> > > > _has to be_ threaded is the kernel, everything else is easier to
> > > > parallelize on a task basis: don't waste time degeloping, say, 1024-CPU
> > > > parallelized gzip - instead, run thousands of gzip copies!
> > >
> > > Which then wind up talking to each other through pipes or fifos or
> > > sockets, and you have a scalability bottleneck in a select statement
> > > sending the data back. Less so now with the new pipe infrastructure, but
> > > still, you have to copy data between process contexts because fiddling
> > > with page tables for non-persistent shared memory is _more_ expensive
> > > than copying, and it's a cache flush either way...
> >
> > No, not _those_ tasks. Bigger tasks. When you run gzip, you run it as a
> > part of a larger "task to accomplish something". E.g. maybe you are
> > processing Mars Reconnaissance Orbiter photos, and archiving step in
> > pipeline compresses them.
>
> You mean the way the aboriginal build scripts often take a FORK=1 environment
> variable that will, for example, make ./download.sh download and extract each
> tarball in parallel?
>
> There are a bunch of ways to achieve parallelism. Threading is one of them.
> Threading doesn't work on beowulf clusters. But some programs really don't
> break down well to beowulf clusters...
>
> > Then, do not bother creating insanely parallelized gzip (and insanely
> > parallelized image analysis software, and insanely parallelized
> > database...); instead, process in parallel *insane number of photos* using
> > run of the mill, simple, *single-threaded* tools.
>
> If you have a task that breaks down that way, sure.
Google did not have a choice. They *had to* scale everything they do,
scale into tens of thousands of subtasks, and they could not affort
waiting thirty years while gzip and gazillion other tools got
parallelized to death. They succeeded, using the above approach.
> > This may even be faster, since you do not need to bother with locks,
> > cacheline bouncing and such.
>
> If you have a task that breaks down that way. Not all tasks do.
>
> > But more importantly, you have so much less complexity and
> > fewer bugs to fix!
>
> If you get to pick which problems you want to solve, you can avoid the messy
> ones.
>
> > (If you do not have insanely many photos to process, but just a few,
> > in most cases today's CPUs are fast enough to not optimize for this case.)
>
> MPEG video compresison in realtime. Each frame is a delta from the previous
> frame, _after_ any changes to the data due to "lossy" compression (which
> can't
> be allowed to accumulate or the image quality goes into the toilet extremely
> rapidly and you have to re-keyframe multiple times per second.)
>
> A lot of signal processing issues are like that. You can chop the signal at
> each keyframe and distribute across a cluster that way, but if your keyframes
> are every 2 seconds then you guarantee that much latency, which sucks for
> videoconferencing and other types of live broadcasts.
>
> That's one program domain out of hundreds for which "redefine the problem
> into
> something I feel like solving" turns out to be hard.
Sure, there _are_ programs which must be threaded. Linux kernel
is another example.
> > if ([!]x) is definitely ok for bool and pointers. For ints,
> > it is sometimes good to write if (x != 0), especially if the code
> > aroud that place is complex-ish and it's hard to figure out
> > the type of x. Not a hard rule.
>
> *blink* *blink*
My failure in English. I meant "It's not a hard rule, though", as in
"not a must". But I suspect it come through as "easy to follow rule".
> You see a significant difference between scalar and pointer types?
This is not the point. The point is:
...
...
...
const re_dfa_t *const dfa = mctx->dfa;
reg_errcode_t err;
int match = 0;
int match_last = -1;
int cur_str_idx = re_string_cur_idx (&mctx->input);
re_dfastate_t *cur_state;
int at_init_state = p_match_first != NULL;
int next_start_idx = cur_str_idx;
err = REG_NOERROR;
cur_state = acquire_init_state_context (&err, mctx, cur_str_idx);
/* An initial state must not be NULL (invalid). */
if (BE (cur_state == NULL, 0))
{
assert (err == REG_ESPACE);
return -2;
}
if (mctx->state_log != NULL)
{
mctx->state_log[cur_str_idx] = cur_state;
/* Check OP_OPEN_SUBEXP in the initial state in case that we use them
later. E.g. Processing back references. */
if (BE (dfa->nbackref, 0))
{
at_init_state = 0;
err = check_subexp_matching_top (mctx, &cur_state->nodes, 0);
if (BE (err != REG_NOERROR, 0))
return err;
if (cur_state->has_backref)
{
err = transit_state_bkref (mctx, &cur_state->nodes);
if (BE (err != REG_NOERROR, 0))
return err;
}
}
}
/* If the RE accepts NULL string. */
if (BE (cur_state->halt, 0))
{
if (!cur_state->has_constraint
|| check_halt_state_context (mctx, cur_state, cur_str_idx))
{
if (!fl_longest_match)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
return cur_str_idx;
else
{
match_last = cur_str_idx;
match = 1;
}
}
}
Rob, can you figure out whether fl_longest_match is a number? or bool?
or maybe a string (that is, char*) in the underlined if() statement?
The problem is that in code like this (and this is not the worst example -
it's only what I found with quick grep in uclibc) you need to grep
for the declaration, it's not easily available. A hint on the type
may be useful.
> A pointer is a scalar type. You can do math on the suckers (admittedly in
> base sizeof(*)).
>
> char *fred="123";
>
> printf("%s", 2+fred);
>
> Prints 3. Nothing special about "fred+2" or "&fred[2]"...
You think 2+"abc" is a weird expression? How about this? -
#include <stdio.h>
int main() { puts(&3["qwerty"]); return 0; }
Hehe ]:)
> Personally I find:
>
> if (strcmp(walrus) == 0);
> {
> thingy()
> }
>
> Harder to spot than:
>
> if (!strcmp(walrus));
> thingy();
Me too, but because of {}s, not because of == 0.
> I've seldom found adding extra characters helps me parse code. But then I
> didn't even put lot of spaces in each line until Erik complained. (And that
> wasn't because I thought it was better, that was just for consistency.)
Iwasusingjammedtogether for(i=0;i<nregs;++i) style for quite some time.
But I eventually changed my mind.
--
vda
_______________________________________________
busybox mailing list
[email protected]
http://lists.busybox.net/mailman/listinfo/busybox
