Re: [Themis-dev] Another code base

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

Raymond C. Rodgers a écrit :
> 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.
You're right.
You are describing an usage pattern, while I was describing a dataflow 
pattern.
To carry on your example, if you have multiple tab, then each tab in UZI 
have its own thread doing successively (parsing / mapping / rendering).
However, the fetcher is shared between threads.

Concerning the picture you're talking about, the URL handler code (in 
Network/URLHandler.hpp) will find by itself that the address (to the 
picture) is a local file, and then fetch it (load from disk) in one of 
the thread pool. Then the cache engine will then determine the file 
type, which will most probably result in JPG picture. As it's not HTML 
or XHTML, the HTML parser will not be called, nor will the DOM mapper, 
only the renderer will be called with a JPG document as source (and not 
a dom tree).

Finally, I haven't paid for the lock overhead in the parser/mapper/renderer.
There is no need to protect data in every tab, as no tab can deal with 
content from other tab.
I'm paying for locking overhead in the fetcher (so each call to the 
fetcher are serialized).

Surely, when only one tab is open or actively used (as it's the case for 
most of the time), the time to see a document in UZI requires that the 
parser finished parsing, the mapper finished mapping, and the renderer 
finished, well, rendering.

In your structure, you are correct about this, the renderer will start 
displaying data while the parser hasn't finished parsing, at the cost of 
data synchronization, and rerendering when everything is 
received/parsed. It might be more "reactive" to user POV, but at the 
same time very very more difficult for the dev POV.

>> 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.
I disagree on that point. All the networking functions are reentrant, 
provided you use a recent libc, as it's a POSIX requirement.
However, I agree on the fact that it's not because the function are 
reentrant that it's possible to call them without locking your data first.
The fetcher locks the data while it fetches them, and release it while 
it's "select"ing the socket. That way, it's possible to get some stats 
on the communication, and, in a later step, start parsing the received 
data while receiving them.
However, the finer the locking mechanism is, the longer you'll loose in 
system time.

In UZI, I've choosen the minimum possible locking.
I understand your choices through, but warn you about the difficulties 
you'll encounter (specially the about the parsing error leading to full 
rework of the DOM tree, hence current rendering, and so on).
Sometime it's easier to complexify a simple design than doing the opposite.

Cyril