Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #66456 > unrolled thread

setjmp, longjmp, parser state, threads

Back to article view | Back to comp.lang.c

Contents

  setjmp, longjmp, parser state, threads "Morten W. Petersen" <morphex@gmail.com> - 2015-07-27 20:50 +0200
    Re: setjmp, longjmp, parser state, threads Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-07-28 00:22 +0100
      Re: OT - XML Parallel Parsing, was [Re: setjmp, longjmp, parser state, threads] Jeff Higgins <jeff@invalid.invalid> - 2015-07-27 21:00 -0400
        Re: OT - XML Parallel Parsing, was [Re: setjmp, longjmp, parser state,   threads] Ian Collins <ian-news@hotmail.com> - 2015-07-28 13:57 +1200
          Re: OT - XML Parallel Parsing, was [Re: setjmp, longjmp, parser state,   threads] Jeff Higgins <jeff@invalid.invalid> - 2015-07-27 22:13 -0400
            Re: OT - XML Parallel Parsing, was [Re: setjmp, longjmp, parser state,     threads] Ian Collins <ian-news@hotmail.com> - 2015-07-28 17:12 +1200
              Re: OT - XML Parallel Parsing Jeff Higgins <jeff@invalid.invalid> - 2015-07-28 09:46 -0400
            Re: OT - XML Parallel Parsing, was [Re: setjmp, longjmp, parser state, threads] "Morten W. Petersen" <morphex@gmail.com> - 2015-07-28 10:07 +0200
              Re: OT - XML Parallel Parsing, was [Re: setjmp, longjmp, parser state, threads] raltbos@xs4all.nl (Richard Bos) - 2015-07-28 09:28 +0000
                Patents, was [Re: OT - XML Parallel Parsing, was [Re: setjmp, longjmp, parser state, threads]] "Morten W. Petersen" <morphex@gmail.com> - 2015-07-28 11:41 +0200
                  Re: Patents, was [Re: OT - XML Parallel Parsing, was [Re: setjmp, longjmp, parser state, threads]] Stephen Sprunk <stephen@sprunk.org> - 2015-07-28 20:53 -0500
                    Re: Patents, was [Re: OT - XML Parallel Parsing, was [Re: setjmp, longjmp, parser state, threads]] "Morten W. Petersen" <morphex@gmail.com> - 2015-07-29 05:15 +0200
                    Re: Patents, was [Re: OT - XML Parallel Parsing, was [Re: setjmp, longjmp, parser state, threads]] Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2015-07-28 22:34 -0600
        Re: OT - XML Parallel Parsing, was [Re: setjmp, longjmp, parser state, threads] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-07-28 03:06 +0100
      Re: setjmp, longjmp, parser state, threads "Morten W. Petersen" <morphex@gmail.com> - 2015-07-28 10:44 +0200
        Re: setjmp, longjmp, parser state, threads Ian Collins <ian-news@hotmail.com> - 2015-07-28 22:14 +1200
          Re: setjmp, longjmp, parser state, threads "Morten W. Petersen" <morphex@gmail.com> - 2015-07-28 15:17 +0200
        Re: setjmp, longjmp, parser state, threads Jeff Higgins <jeff@invalid.invalid> - 2015-07-28 08:35 -0400
        Re: setjmp, longjmp, parser state, threads James Kuyper <jameskuyper@verizon.net> - 2015-07-28 10:29 -0400
          Re: setjmp, longjmp, parser state, threads "Morten W. Petersen" <morphex@gmail.com> - 2015-07-28 16:39 +0200
    Re: setjmp, longjmp, parser state, threads jadill33@gmail.com - 2015-07-28 06:47 -0700
      Re: setjmp, longjmp, parser state, threads "Morten W. Petersen" <morphex@gmail.com> - 2015-07-28 16:56 +0200
        Re: setjmp, longjmp, parser state, threads Noob <root@127.0.0.1> - 2015-07-28 18:04 +0200
        Re: setjmp, longjmp, parser state, threads jadill33@gmail.com - 2015-07-28 10:53 -0700
          Re: setjmp, longjmp, parser state, threads "Morten W. Petersen" <morphex@gmail.com> - 2015-07-29 04:59 +0200
    Re: setjmp, longjmp, parser state, threads Bartc <bc@freeuk.com> - 2015-07-28 16:29 +0100

Page 1 of 2  [1] 2  Next page →

#66456 — setjmp, longjmp, parser state, threads

Hi there. :)

I'm writing an XML parser, which will also be built to support threads.

Now, I've been looking at bit at threads, parser state, setjmp and
longjmp.

Threads will be an important optional feature to minimize the amount of
time it takes to parse an XML file.

I haven't used setjmp and longjmp before, but it looks like some
variable has to be passed around, something I was thinking (or
hoping) it wouldn't.  It also looks like it saves the current
state of the program on setjmp, and I don't know how threads
would mix with that.

So far, threading is a feature that will speed things up, but
it will also complicate things.  So my plan is to have a parser
object (with an error flag and a pointer to the buffer) that will
be passed around.  And if any intolerable error pops up when parsing
the XML, the error flag will be set on the parser object.  The parser
will also have a Unicode string pointer that points to an explanation
of what went wrong.

If an error pops up that can't be handled, just jump out of the parsing
at the earliest and flag an error.  Multiple threads might encounter
errors and flip the flag to something else than 0, and multiple threads
might set an error message.

Now, the point of the parser isn't to parse an XML document and point
out all the errors. The point is to parse things correct, fast and
as efficiently as possible.  If one or the other message pops up
with the error that's good enough for now.

Now, the flag and Unicode string pointer will have to be thread-safe,
so it must be possible to lock them..  that's fine and OK.

Am I right in thinking that since the program will use threads at some
point, it is a good idea to have a parser object instead of a setjmp /
longjmp thing?

The project is here:

https://github.com/morphex/smash_xml

-Morten

[toc] | [next] | [standalone]

#66463

"Morten W. Petersen" <morphex@gmail.com> writes:
<snip>
> I'm writing an XML parser, which will also be built to support
> threads.

That's a good idea.  Pretty much all utility code should aim to be
thread safe or thread aware.  (I'm not being sarky -- I know that may
not be what you mean by "support" but it will be a valuable consequence
of any consideration of threads.)

> Now, I've been looking at bit at threads, parser state, setjmp and
> longjmp.
>
> Threads will be an important optional feature to minimize the amount of
> time it takes to parse an XML file.

This is not an obvious fact that you can just assert.  You may have some
evidence for it, but if not I think you should try it out first as I
suggest below

<snip>
> Am I right in thinking that since the program will use threads at some
> point, it is a good idea to have a parser object instead of a setjmp /
> longjmp thing?

You should have a parse object to reflect the state of the parse (error
flags included) because that's the right thing to do anyway.  And you
should generally avoid setjmp and longjmp unless they are forced on you
(i.e. they appear to be the only way out of some serious design
problem).  Support for threading does make the arguments for a parse
object and against setjmp/longjmp a bit stronger, but it's not the
reason to make that choice.

As for using threads for parsing XML, I suggest you try an experiment.
Write a throw-away threaded program the builds a tree structure from
some text input (you can invent your own to be favourable to threaded
parsing) and see if you can indeed make it as fasted than a non-threaded
version.  You've decided that threads will make parsing faster, but I
find that hard to believe though I'd love to see that preconception
overturned.

Such an experimental program would teach you a lot about writing
threaded code (I think you are new to that from what you've written) and
it would force you to think about how parsing can be broken up into
suitable work units (which it one of the barriers I have to thinking
that there is any value in using threads).  Both of those would be
valuable to you even if the code is eventually thrown away.

But the big point is that either you'll learn that threads are not a
good match to this problem (and that's a big win for you if it's true),
or I'll learn that I've got an unhelpful mental picture model of what
threads can do (that's less of a win for you, but you'll have done me a
service).  Surely all of that is worth a short experiment?

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#66465 — Re: OT - XML Parallel Parsing, was [Re: setjmp, longjmp, parser state, threads]

On 07/27/2015 07:22 PM, Ben Bacarisse wrote:
<snip>
> it would force you to think about how parsing can be broken up into
> suitable work units (which it one of the barriers I have to thinking
> that there is any value in using threads).
<snip>
A Review of XML Parallel Parsing Techniques
<http://www.ijcsmc.com/docs/papers/April2014/V3I4201499b68.pdf>

[toc] | [prev] | [next] | [standalone]

#66466 — Re: OT - XML Parallel Parsing, was [Re: setjmp, longjmp, parser state, threads]

Jeff Higgins wrote:
> On 07/27/2015 07:22 PM, Ben Bacarisse wrote:
> <snip>
>> it would force you to think about how parsing can be broken up into
>> suitable work units (which it one of the barriers I have to thinking
>> that there is any value in using threads).
> <snip>
> A Review of XML Parallel Parsing Techniques
> <http://www.ijcsmc.com/docs/papers/April2014/V3I4201499b68.pdf>

Interesting paper, thanks for the link.

I have experimented with what the paper describes as a Parallel XML 
Parser (PXP) and with my data set (large ODF documents), the gains 
didn't outweigh the costs.  The biggest cost was synchronising access to 
the DOM tree (and the memory pool).  I'd previously worked on minimising 
cache misses when building the tree and this didn't sit well with 
parallel parsing.  Maybe choosing different internal representation 
would help, but I can't help feeling optimisations for serial and 
parallel parsing are orthogonal.

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#66469 — Re: OT - XML Parallel Parsing, was [Re: setjmp, longjmp, parser state, threads]

On 07/27/2015 09:57 PM, Ian Collins wrote:
> Jeff Higgins wrote:
>> On 07/27/2015 07:22 PM, Ben Bacarisse wrote:
>> <snip>
>>> it would force you to think about how parsing can be broken up into
>>> suitable work units (which it one of the barriers I have to thinking
>>> that there is any value in using threads).
>> <snip>
>> A Review of XML Parallel Parsing Techniques
>> <http://www.ijcsmc.com/docs/papers/April2014/V3I4201499b68.pdf>
>
> Interesting paper, thanks for the link.
>
> I have experimented with what the paper describes as a Parallel XML
> Parser (PXP) and with my data set (large ODF documents), the gains
> didn't outweigh the costs.  The biggest cost was synchronising access to
> the DOM tree (and the memory pool).  I'd previously worked on minimising
> cache misses when building the tree and this didn't sit well with
> parallel parsing.  Maybe choosing different internal representation
> would help, but I can't help feeling optimisations for serial and
> parallel parsing are orthogonal.
>

<http://www.google.com/patents/US8739022>

Another paper - I've lost the link - asserts Parallel XML Parser (PXP)
is unsuited to large documents.

[toc] | [prev] | [next] | [standalone]

#66477 — Re: OT - XML Parallel Parsing, was [Re: setjmp, longjmp, parser state, threads]

Jeff Higgins wrote:
> On 07/27/2015 09:57 PM, Ian Collins wrote:
>> Jeff Higgins wrote:
>>> On 07/27/2015 07:22 PM, Ben Bacarisse wrote:
>>> <snip>
>>>> it would force you to think about how parsing can be broken up into
>>>> suitable work units (which it one of the barriers I have to thinking
>>>> that there is any value in using threads).
>>> <snip>
>>> A Review of XML Parallel Parsing Techniques
>>> <http://www.ijcsmc.com/docs/papers/April2014/V3I4201499b68.pdf>
>>
>> Interesting paper, thanks for the link.
>>
>> I have experimented with what the paper describes as a Parallel XML
>> Parser (PXP) and with my data set (large ODF documents), the gains
>> didn't outweigh the costs.  The biggest cost was synchronising access to
>> the DOM tree (and the memory pool).  I'd previously worked on minimising
>> cache misses when building the tree and this didn't sit well with
>> parallel parsing.  Maybe choosing different internal representation
>> would help, but I can't help feeling optimisations for serial and
>> parallel parsing are orthogonal.
>>
>
> <http://www.google.com/patents/US8739022>

I wonder if my experiments pre-date theirs...

> Another paper - I've lost the link - asserts Parallel XML Parser (PXP)
> is unsuited to large documents.

I've also looked at parallel parsing large JSON documents and the same 
issues arise there.  If pushed I'd say most XML parsing is done with two 
types of file: office documents and web service requests.  The former 
probably take longer to organise and render than to parse and the latter 
tend to be small.  I guess I should include XHTML pages, but these also 
take longer to organise and render than to parse.

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#66493 — Re: OT - XML Parallel Parsing

On 07/28/2015 01:12 AM, Ian Collins wrote:
<snip>
> I've also looked at parallel parsing large JSON documents and the same
> issues arise there.  If pushed I'd say most XML parsing is done with two
> types of file: office documents and web service requests.  The former
> probably take longer to organise and render than to parse and the latter
> tend to be small.  I guess I should include XHTML pages, but these also
> take longer to organise and render than to parse.

I ordered an out of print book.
The bookseller was careful to package the book so as
to avoid damage in shipment. Unpacking the book became
a struggle, involving scissors, ... and almost upsetting
a coffee cup. The author of the book arranged his
material such that I am forced to read one chapter and
understand it before I am able to proceed to the next.
I'm still working on it - several weeks later.

I received a gift box of assorted goodies.
The packaging was clumsy as well. Unfortunately I had
a significant pool of eager "worker threads" available
at the moment and the contents were consumed quickly.

[toc] | [prev] | [next] | [standalone]

#66479 — Re: OT - XML Parallel Parsing, was [Re: setjmp, longjmp, parser state, threads]

On 28.07.2015 04:13, Jeff Higgins wrote:
> On 07/27/2015 09:57 PM, Ian Collins wrote:
>> Jeff Higgins wrote:
>>> On 07/27/2015 07:22 PM, Ben Bacarisse wrote:
>>> <snip>
>>>> it would force you to think about how parsing can be broken up into
>>>> suitable work units (which it one of the barriers I have to thinking
>>>> that there is any value in using threads).
>>> <snip>
>>> A Review of XML Parallel Parsing Techniques
>>> <http://www.ijcsmc.com/docs/papers/April2014/V3I4201499b68.pdf>
>>
>> Interesting paper, thanks for the link.
>>
>> I have experimented with what the paper describes as a Parallel XML
>> Parser (PXP) and with my data set (large ODF documents), the gains
>> didn't outweigh the costs.  The biggest cost was synchronising access to
>> the DOM tree (and the memory pool).  I'd previously worked on minimising
>> cache misses when building the tree and this didn't sit well with
>> parallel parsing.  Maybe choosing different internal representation
>> would help, but I can't help feeling optimisations for serial and
>> parallel parsing are orthogonal.
>>
>
> <http://www.google.com/patents/US8739022>
>
> Another paper - I've lost the link - asserts Parallel XML Parser (PXP)
> is unsuited to large documents.

I'll try not to read anything like that above, to avoid being caught up
in whatever thought pattern the author, or authors, have.

This patent thing opens up another can of worms, hopefully will a
history on GitHub and comp.lang.c scare anyone who wants to run away
with whatever unique thing I might come up with as a patent.

One thing is having legal muscle, another is to look like a moron.

-Morten

[toc] | [prev] | [next] | [standalone]

#66484 — Re: OT - XML Parallel Parsing, was [Re: setjmp, longjmp, parser state, threads]

"Morten W. Petersen" <morphex@gmail.com> wrote:

> On 28.07.2015 04:13, Jeff Higgins wrote:

> > <http://www.google.com/patents/US8739022>
> >
> > Another paper - I've lost the link - asserts Parallel XML Parser (PXP)
> > is unsuited to large documents.
> 
> I'll try not to read anything like that above, to avoid being caught up
> in whatever thought pattern the author, or authors, have.
> 
> This patent thing opens up another can of worms, hopefully will a
> history on GitHub and comp.lang.c scare anyone who wants to run away
> with whatever unique thing I might come up with as a patent.
> 
> One thing is having legal muscle, another is to look like a moron.

Sadly, when it comes to software patents, sufficient legal muscle means
you never have to admit you look like a moron until you run into someone
with even more legal muscle. (See also: Apple.)

Richard

[toc] | [prev] | [next] | [standalone]

#66486 — Patents, was [Re: OT - XML Parallel Parsing, was [Re: setjmp, longjmp, parser state, threads]]

On 28.07.2015 11:28, Richard Bos wrote:
> "Morten W. Petersen" <morphex@gmail.com> wrote:
>
>> On 28.07.2015 04:13, Jeff Higgins wrote:
>
>>> <http://www.google.com/patents/US8739022>
>>>
>>> Another paper - I've lost the link - asserts Parallel XML Parser (PXP)
>>> is unsuited to large documents.
>>
>> I'll try not to read anything like that above, to avoid being caught up
>> in whatever thought pattern the author, or authors, have.
>>
>> This patent thing opens up another can of worms, hopefully will a
>> history on GitHub and comp.lang.c scare anyone who wants to run away
>> with whatever unique thing I might come up with as a patent.
>>
>> One thing is having legal muscle, another is to look like a moron.
>
> Sadly, when it comes to software patents, sufficient legal muscle means
> you never have to admit you look like a moron until you run into someone
> with even more legal muscle. (See also: Apple.)

Well I know if I get into something like that, I'll probably blog and
tweet about it.

It would be nice if some legal experts would dissect these cases and
tell what's really going on, then the rest of us could talk about it
and know which companies to avoid working for or buying products from.

Realistically though, it looks like at some level this is a game that
big companies play, and that it is very unlikely that big companies
will go after "the little guy".

I'm more worried about various lesser known companies that can work
on big company agendas or even other people's personal agendas without
it being obvious.  Or people that have found a rather dubious way of
making money.

-Morten

[toc] | [prev] | [next] | [standalone]

#66516 — Re: Patents, was [Re: OT - XML Parallel Parsing, was [Re: setjmp, longjmp, parser state, threads]]

On 28-Jul-15 04:41, Morten W. Petersen wrote:
> On 28.07.2015 11:28, Richard Bos wrote:
>> Sadly, when it comes to software patents, sufficient legal muscle
>> means you never have to admit you look like a moron until you run
>> into someone with even more legal muscle. (See also: Apple.)
> 
> Well I know if I get into something like that, I'll probably blog
> and tweet about it.
> 
> It would be nice if some legal experts would dissect these cases and 
> tell what's really going on, then the rest of us could talk about it 
> and know which companies to avoid working for or buying products
> from.
> 
> Realistically though, it looks like at some level this is a game
> that big companies play, and that it is very unlikely that big
> companies will go after "the little guy".

The software industry has collectively agreed that the very idea of
software patents is bogus and uses them mainly for defensive purposes.
Cross-licensing agreements are common, even if one side has hundreds or
even thousands of patents and the other (currently) has zero.  Actual
lawsuits between vendors are extremely rare.

> I'm more worried about various lesser known companies that can work 
> on big company agendas or even other people's personal agendas
> without it being obvious.  Or people that have found a rather dubious
> way of making money.

The problem is "patent trolls" who buy up patents (mostly from defunct
companies), sit on them for years while software vendors unknowingly
violate those patents, and then pop up and sue everyone.  Since they
make nothing themselves, there is no cross-licensing and no way for the
victims to countersue.

Many companies will just pay trolls to go away because it's cheaper than
beating them in court--and that's what they're counting on.  The major
vendors will often take them to court, even though it costs them more in
the short run, as a matter of principle--and to rack up precedents in
their favor for the long run.

S

-- 
Stephen Sprunk         "God does not play dice."  --Albert Einstein
CCIE #3723         "God is an inveterate gambler, and He throws the
K5SSS        dice at every possible opportunity." --Stephen Hawking

[toc] | [prev] | [next] | [standalone]

#66518 — Re: Patents, was [Re: OT - XML Parallel Parsing, was [Re: setjmp, longjmp, parser state, threads]]

On 29.07.2015 03:53, Stephen Sprunk wrote:
> On 28-Jul-15 04:41, Morten W. Petersen wrote:
[...]
>> Realistically though, it looks like at some level this is a game
>> that big companies play, and that it is very unlikely that big
>> companies will go after "the little guy".
>
> The software industry has collectively agreed that the very idea of
> software patents is bogus and uses them mainly for defensive purposes.
> Cross-licensing agreements are common, even if one side has hundreds or
> even thousands of patents and the other (currently) has zero.  Actual
> lawsuits between vendors are extremely rare.

Lawsuits are one thing.  Hints about lawsuits and other techniques to
"negotiate" are another.

It seems fair that a person or an organization that puts a lot of time
and effort into creating something new, should be rewarded for it.

However, it looks to me like it is hard to discern what can be called
"patent land-grabbing" and what is genuinely new ground.

>> I'm more worried about various lesser known companies that can work
>> on big company agendas or even other people's personal agendas
>> without it being obvious.  Or people that have found a rather dubious
>> way of making money.
>
> The problem is "patent trolls" who buy up patents (mostly from defunct
> companies), sit on them for years while software vendors unknowingly
> violate those patents, and then pop up and sue everyone.  Since they
> make nothing themselves, there is no cross-licensing and no way for the
> victims to countersue.
>
> Many companies will just pay trolls to go away because it's cheaper than
> beating them in court--and that's what they're counting on.  The major
> vendors will often take them to court, even though it costs them more in
> the short run, as a matter of principle--and to rack up precedents in
> their favor for the long run.

Well, from a political standpoint, it would seem the main reason
patents exist is that they should foster innovation and inventions.

That they can be abused is like many other things in life, I guess
if it becomes a big enough problem the system will be changed to
deal with it.

-Morten

[toc] | [prev] | [next] | [standalone]

#66519 — Re: Patents, was [Re: OT - XML Parallel Parsing, was [Re: setjmp, longjmp, parser state, threads]]

Stephen Sprunk <stephen@sprunk.org> writes:
>
> The software industry has collectively agreed that the very idea of
> software patents is bogus and uses them mainly for defensive purposes.
> Cross-licensing agreements are common, even if one side has hundreds or
> even thousands of patents and the other (currently) has zero.  Actual
> lawsuits between vendors are extremely rare.

While I've seen lots of stories of big cross-licensing agreements, I'd
be very happy to see something concrete to the effect that the industry
has really decided they're bogus.

What's Microsoft being paid per Android installation, due to their
patents, these days?  I don't remember numbers, but I do remember at one
point the cost to license Android from Microsoft (who, don't forget, had
absolutely nothing to do with Android development) was higher then the
cost to license Windows Mobile.

[toc] | [prev] | [next] | [standalone]

#66467 — Re: OT - XML Parallel Parsing, was [Re: setjmp, longjmp, parser state, threads]

Jeff Higgins <jeff@invalid.invalid> writes:

> On 07/27/2015 07:22 PM, Ben Bacarisse wrote:
> <snip>
>> it would force you to think about how parsing can be broken up into
>> suitable work units (which it one of the barriers I have to thinking
>> that there is any value in using threads).
> <snip>
> A Review of XML Parallel Parsing Techniques
> <http://www.ijcsmc.com/docs/papers/April2014/V3I4201499b68.pdf>

Thanks.  Looks like one would have to read all the sources since the
review itself is startlingly devoid of data on timings and methods.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#66481

On 28.07.2015 01:22, Ben Bacarisse wrote:
> "Morten W. Petersen" <morphex@gmail.com> writes:
> <snip>
>> I'm writing an XML parser, which will also be built to support
>> threads.
>
> That's a good idea.  Pretty much all utility code should aim to be
> thread safe or thread aware.  (I'm not being sarky -- I know that may
> not be what you mean by "support" but it will be a valuable consequence
> of any consideration of threads.)
>
>> Now, I've been looking at bit at threads, parser state, setjmp and
>> longjmp.
>>
>> Threads will be an important optional feature to minimize the amount of
>> time it takes to parse an XML file.
>
> This is not an obvious fact that you can just assert.  You may have some
> evidence for it, but if not I think you should try it out first as I
> suggest below

Well I've gathered that threads aren't necessarily the one right way to
reduce the time it takes to complete a task.

> <snip>
>> Am I right in thinking that since the program will use threads at some
>> point, it is a good idea to have a parser object instead of a setjmp /
>> longjmp thing?
>
> You should have a parse object to reflect the state of the parse (error
> flags included) because that's the right thing to do anyway.  And you
> should generally avoid setjmp and longjmp unless they are forced on you
> (i.e. they appear to be the only way out of some serious design
> problem).  Support for threading does make the arguments for a parse
> object and against setjmp/longjmp a bit stronger, but it's not the
> reason to make that choice.
>
> As for using threads for parsing XML, I suggest you try an experiment.
> Write a throw-away threaded program the builds a tree structure from
> some text input (you can invent your own to be favourable to threaded
> parsing) and see if you can indeed make it as fasted than a non-threaded
> version.  You've decided that threads will make parsing faster, but I
> find that hard to believe though I'd love to see that preconception
> overturned.

I was thinking of handing off certain parts of the parsing to
specialized functions, so that for example the starting element tag in
XML with all its attributes can be handled by a separate thread and
then the main thread can proceed to the element content.

Another is having a thread read from the stream and build an internal
representation of the incoming XML data and have another thread work
on that representation.

But it looks like the smartest thing to do is to make everything fast
without threading first, and maybe analyze distinct parts of the
parsing, having a file completely read into memory before "the real
work starts" for example.

> Such an experimental program would teach you a lot about writing
> threaded code (I think you are new to that from what you've written) and
> it would force you to think about how parsing can be broken up into
> suitable work units (which it one of the barriers I have to thinking
> that there is any value in using threads).  Both of those would be
> valuable to you even if the code is eventually thrown away.

Yes, maybe I'll do that.  It might be a little bit too theoretical
though and more gratifying to start using threads in the parser instead.

> But the big point is that either you'll learn that threads are not a
> good match to this problem (and that's a big win for you if it's true),
> or I'll learn that I've got an unhelpful mental picture model of what
> threads can do (that's less of a win for you, but you'll have done me a
> service).  Surely all of that is worth a short experiment?

Short snippets of code are good for a theoretical understanding of
something, but I think I understand threads well enough.  There is
a small memory cost, some cost of context switching and managing
threads, and working with large data sets can for example be slow
because it is outside of the CPU cache.

Is there anything else to consider using threads?

-Morten

[toc] | [prev] | [next] | [standalone]

#66488

Morten W. Petersen wrote:
>
> Short snippets of code are good for a theoretical understanding of
> something, but I think I understand threads well enough.  There is
> a small memory cost, some cost of context switching and managing
> threads, and working with large data sets can for example be slow
> because it is outside of the CPU cache.
>
> Is there anything else to consider using threads?

Synchronisation.

If you have a number of threads building a shared data structure (an XML 
DOM for example), contention for locks on that structure can be a real 
performance killer, especially if it contains many small nodes.
-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#66490

On 28.07.2015 12:14, Ian Collins wrote:
> Morten W. Petersen wrote:
>>
>> Short snippets of code are good for a theoretical understanding of
>> something, but I think I understand threads well enough.  There is
>> a small memory cost, some cost of context switching and managing
>> threads, and working with large data sets can for example be slow
>> because it is outside of the CPU cache.
>>
>> Is there anything else to consider using threads?
>
> Synchronisation.
>
> If you have a number of threads building a shared data structure (an XML
> DOM for example), contention for locks on that structure can be a real
> performance killer, especially if it contains many small nodes.

Ah yes.  That can mostly be designed out as well I guess.

As for parsing, it looks like data structures that have been
completed can be marked as such using a simple flag, for example
that one of the pointers is pointing somewhere and is not NULL.

But again, at the synchronization point after the parsing, one
can just check that none of the threads are busy and then continue
and save that overhead.

-Morten

[toc] | [prev] | [next] | [standalone]

#66489

On 07/28/2015 04:44 AM, Morten W. Petersen wrote:

<snip>
> Short snippets of code are good for a theoretical understanding of
> something, but I think I understand threads well enough.  There is
> a small memory cost, some cost of context switching and managing
> threads, and working with large data sets can for example be slow
> because it is outside of the CPU cache.
>
> Is there anything else to consider using threads?

Designing Threaded Programs
<https://computing.llnl.gov/tutorials/pthreads/#Designing>

[toc] | [prev] | [next] | [standalone]

#66494

On 07/28/2015 04:44 AM, Morten W. Petersen wrote:
> On 28.07.2015 01:22, Ben Bacarisse wrote:
>> "Morten W. Petersen" <morphex@gmail.com> writes:
>> <snip>
>>> I'm writing an XML parser, which will also be built to support
>>> threads.
>>
>> That's a good idea.  Pretty much all utility code should aim to be
>> thread safe or thread aware.  (I'm not being sarky -- I know that may
>> not be what you mean by "support" but it will be a valuable consequence
>> of any consideration of threads.)
>>
>>> Now, I've been looking at bit at threads, parser state, setjmp and
>>> longjmp.
>>>
>>> Threads will be an important optional feature to minimize the amount of
>>> time it takes to parse an XML file.
>>
>> This is not an obvious fact that you can just assert.  You may have some
>> evidence for it, but if not I think you should try it out first as I
>> suggest below
> 
> Well I've gathered that threads aren't necessarily the one right way to
> reduce the time it takes to complete a task.

That's a start in the right direction. But you should also understand
that threads can be a very efficient and effective way of radically
increasing the amount of time it takes to complete a task. Creating a
new thread which either has too little work of it's own to do, or which
must spend too large a fraction of it's time coordinating its work with
other threads, can really ruin the performance of a program.
-- 
James Kuyper

[toc] | [prev] | [next] | [standalone]

#66495

On 28.07.2015 16:29, James Kuyper wrote:
> On 07/28/2015 04:44 AM, Morten W. Petersen wrote:
>> On 28.07.2015 01:22, Ben Bacarisse wrote:
>>> "Morten W. Petersen" <morphex@gmail.com> writes:
>>> <snip>
>>>> I'm writing an XML parser, which will also be built to support
>>>> threads.
>>>
>>> That's a good idea.  Pretty much all utility code should aim to be
>>> thread safe or thread aware.  (I'm not being sarky -- I know that may
>>> not be what you mean by "support" but it will be a valuable consequence
>>> of any consideration of threads.)
>>>
>>>> Now, I've been looking at bit at threads, parser state, setjmp and
>>>> longjmp.
>>>>
>>>> Threads will be an important optional feature to minimize the amount of
>>>> time it takes to parse an XML file.
>>>
>>> This is not an obvious fact that you can just assert.  You may have some
>>> evidence for it, but if not I think you should try it out first as I
>>> suggest below
>>
>> Well I've gathered that threads aren't necessarily the one right way to
>> reduce the time it takes to complete a task.
>
> That's a start in the right direction. But you should also understand
> that threads can be a very efficient and effective way of radically
> increasing the amount of time it takes to complete a task. Creating a
> new thread which either has too little work of it's own to do, or which
> must spend too large a fraction of it's time coordinating its work with
> other threads, can really ruin the performance of a program.

Yeah..  well, I've been thinking about threads and all that jazz, and
to me it looks like compiling the same code, with/without #defines &
threads and then making a runtime abstraction for which function to
call (based on file size for example) could be the right way to go.

For very small files, firing up a thread seems like it could take
longer than it would take to parse the entire file without threads.

-Morten

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.c

csiph-web