Re: [Themis-dev] Another code base

SourceForge Headquarters 1320 Columbia Street Suite 310 San Diego, CA 92101 +1 (858) 422-6466

Cyril Russo wrote:
> Well, here are the papers I'm referring about:
> http://www.cs.umass.edu/%7Eemery/pubs/berger-oopsla2002.pdf  (about 
> using an allocator can speed up the allocation time by 40%)
> And the older one:
> http://www.cs.umass.edu/%7Eemery/pubs/berger-pldi2001.pdf (a basic 
> example on heap layers)
>
> I have nothing about threading a parser. However, speaking about data 
> flow, I would say that:
>   For the rendering to be done, you need the entire DOM tree (just think 
> of absolutely positioned or floating elements for one). You also need 
> all the linked resources (whatever, CSS, IMG, etc...)
>   For the DOM tree to be entire, you need HTML source to be entire.
>   For the CSS resource, you also need HTML source to be entire (as, even 
> if <style> tag is only allowed in <head>, it's very frequent to find 
> them in the body, google is a nice example of that).
>  
> So yes, surely, you can start parsing an HTML stream, and start making a 
> (partial) DOM tree from it, and still start rendering it, all at the 
> same time.
> However, if there is a table in the page, you'll break everything not 
> waiting for table end (as table size is computable only when received 
> entirely), and table based layout at clearly too frequent to be ignored.
> For example, a <p> tag inside a <table> tag should be rendered before 
> the table (it's illegal, but that's how Mozilla and IE does).
> If there is some JS, then you'll also have to get the whole things 
> before rendering as JS usually deals with DOM tree (so it has to be 
> entire if you don't want your JS engine to fail)
> Finally, rendering prematuraly usually gives the flashing effect you had 
> on Firefox 1.0 when the CSS didn't loaded in time (the <entire> DOM tree 
> rendered, then the CSS arrived, and the <entire> DOM tree rerendered, 
> moving things around).
>
> Anyway, I don't get the interest of multithreading the parser & renderer 
> (mainly for complexifying the parser, because of the multiple locks 
> required to avoid data contention) if you are not going to render the 
> final page until all steps are done.
> On single core CPU, you'll never get any improvment (well, dataflow 
> analysis), and on multicore CPU, the locking mechanism (and bad cache 
> data) might simply break any gain you're expecting (as, at best, the 
> rendering time will be : max(parser time (you need the whole document 
> here), fetching time (way longer that anything else), CSS-DOM mapping, 
> renderer) so it's likely = to fetching time)
>
>   
I'm not an expert on anything, period. But it seems logical to me that a 
document could be rendered more quickly with two threads than with a 
single one if the operating system's scheduler is designed with 
multithreading in mind, as BeOS was. I have seen performance 
improvements in BeOS applications when adding a second thread performing 
the same functionality, if for no other reason than the BeOS scheduler 
sees it as another item that needs attention before it begins cycling 
through the process list again. Besides the idea of attempting to render 
more than one part of a document at a time with multiple threads, 
there's also the more practical reality of adding threads to the parser 
and renderer: multiple simultaneous documents. When dealing with 
Firefox,  IE 7, or Opera 9, it is not uncommon to open multiple 
documents simultaneously. If you have a parser that is not 
multithreaded, you end up with a queue system where each document must 
be processed sequentially, and then rendered sequentially.

Take this example, you open a bookmark that opens 3 tabs automatically. 
Tab 1 opens cnn.com, tab 2 opens slashdot.org, and tab 3 opens an image 
stored on your hard drive. Without being multithreaded, the browser 
might have to wait for cnn.com and slashdot.org to be retrieved, parsed, 
and rendered before it could load the image from your hard disk. Or, 
assuming that your retrieval system is multithreaded, and renders 
whatever is completely retrieved first, you still end up waiting for one 
tab to be completely done before the next can be completed. This example 
obviously isn't completely practical, as no one can read multiple tabs 
simultaneously, but the point is still the same: being multithreaded 
allows multiple documents to be parsed and rendered simultaneously.

As for the messaging system and event driven application design, I agree 
with Mark in that it serves our purposes better. In the same example as 
above, the image in tab 3 has no need to go through a SGML/HTML/XML 
parser. It's an image, and we know it's an image, why do we need to send 
it there? In the design we used with Themis, and will be implementing in 
the renderer and image handler, the image handler will see that an image 
document has been retrieved and will process it for the renderer, and in 
the process notify the renderer (and anyone else that might be 
interested) that the image is ready to use. The renderer can then use 
the image when it's ready for it, which could be right away in the 
example above.

In the cases of tabs 1 and 2 (cnn.com and slashdot.org respectively), 
the images could be added to the rendered output as they become 
available. The reason I state "as they become available" is simple: when 
I browse the web, I'm usually much more interested in the text content 
of a page than the images or other media unless that's what I'm looking 
for. I'd much rather have CNN's content appear so I can start looking 
for articles that I'm interested in while the images are being loaded 
than having to wait for the whole page (images and all) to be 
completely  retrieved first.
> That why I've implemented multithreaded fetching in UZI, so that the 
> rendering time will be (deterministic), max(fetching time + rendering, 
> parsing + CSS mapping + rendering), and the code still remains clear of 
> locking primitives.
>
>   
You more than likely will need to have locking of some sort in this 
design, especially when dealing with Linux. Sending and receiving data 
should always be done under lock conditions when done in a multithreaded 
fashion to prevent corruption. Many of the networking functions are not 
reentrant, and can easily cause data corruption as a result.

Raymond