cxml-devel June 2006

cxml-devel@common-lisp.net

2 participants
3 discussions

FW: [cxml-devel] characters.lisp improvements
by Nathan Bird 23 Jun '06

23 Jun '06

Allrighty fine, I see how it is. ;-) These patches deprecate characters.lisp in favor of the xml-name-rune-p.lisp. I pulled over #'VALID-NAME-P and #'VALID-NMTOKEN-P that were the new functions in characters.lisp, and these functions now use the ones provided by xml-name-rune-p.lisp. http://www.unwashedmeme.com/cxml/asd-remove-chars.diff (diff to cxml.asd) http://www.unwashedmeme.com/cxml/characters-merge.diff (against xml/xml-name-rune-p.lisp) And characters.lisp can be deleted now. Before doing any of the changes I made sure that #'RUNE-NAME-CHAR-P and #'NAME-RUNE-P functions returned #'EQ results for every character between 0 and +max+. I also changed the compile-time behavior of xml-name-rune-p.lisp, but it should be run-time equivalent(inlined bit-vector lookup). At compile time the code now looks a little bit more like the code in characters.lisp. The special character ranges are now vectors that are separate from the code (the binary search) that examine them, rather than ORing everything together. At compile time it will then evaluate the predicates over every possible value and save the result in a bitvector (this is how it was working before) and garbage collection should be able to reclaim the character-range vectors. This change resulted in the compilation on my machine dropping from ~8.9s to about ~.25s. Changes that might be significant: PREDICATE-TO-BV - (dotimes (i #x10000 r) + (dotimes (i +max+ r) Where +max+ = #xD800. The vector only goes up to max, so there is no point trying any characters above that right? The predicates that use the bit-vector fail for anything above max too. NAME-RUNE-P and NAME-START-RUNE-P (the public inlined functions) - (DEFINLINE NAME-RUNE-P (RUNE) - (SETF RUNE (RUNE-CODE RUNE)) - (AND (<= 0 RUNE ,+max+) - (LOCALLY (DECLARE (OPTIMIZE (SAFETY 0) (SPEED 3))) - (= 1 (SBIT ',(predicate-to-bv #'name-rune-p) - (THE FIXNUM RUNE)))))) + (DEFINLINE NAME-RUNE-P (RUNE) + (SETF RUNE (RUNE-CODE RUNE)) + (LOCALLY (DECLARE (OPTIMIZE (SAFETY 0) (SPEED 3)) + (type fixnum rune)) + (AND (<= 0 RUNE ,+max+) + (= 1 (SBIT ',(predicate-to-bv #'name-rune-p) + RUNE))))) I moved the locally declarations up by a line to include the <= check and declare the type of the rune a little bit earlier (so that <= might be able to take advantage of this). Does anyone know of problems this will cause? TEST RESULTS: Xmlconf:run-all-tests 0/1829 tests failed; 333 tests were skipped Domtest:run-all-tests 0/763 tests failed; 43 tests were skipped Timing the xmlconf tests there wasn't really any significant change in speed or memory. Profiling it showed a bit of a drop in the memory usage, but not by much. For the xmlconf tests, these functions are called a decent amount, but don't contribute all that much to the runtime. These weren't terribly exact tests, but a part of the point here was to try and clean-up and remove some of the duped code. http://www.unwashedmeme.com/cxml/characters-merge-profile.results Heh, at least compilation is faster. Whad'ya think? Nathan (My apologies if you got this twice, it looks like it didn't send the first time.) >-----Original Message----- >From: David Lichteblau [mailto:david@lichteblau.com] >Sent: Tuesday, June 13, 2006 2:02 PM >To: Nathan Bird >Cc: cxml-devel(a)common-lisp.net >Subject: Re: [cxml-devel] characters.lisp improvements > > >However, I have to admit that my characters.lisp duplicates work already >done by Gilbert. Gilbert's functions are in xml-name-rune-p.lisp and >are using inline functions accessing bitvectors. Embarrassingly, I >didn't notice the latter file before writing characters.lisp and then >just stuck a comment into the file instead of fixing it right away. >My apologies for that -- and sorry for writing that comment in german. :-( That's why we have google translate... to get bad translations of offhand comments :-)

1 0

[cxml-devel] Dom-impl improvements
by Nathan Bird 13 Jun '06

13 Jun '06

We are building up a dom in memory as part of some XHTML and XUL generation. Found time/memory being spent in append-child which we make heavy use of. Here are some changes that improve this. The children of a node are stored in a node-list (adjustable vector). Changes involved: -Don't allocate a node list until we actually HAVE children -When allocating a node-list, go ahead and make it 4 elements long (instead of 0) so we don't immediately reallocate, and again. -When vector-push-extending. Let the lisp implementation take care of increasing the size, instead of manually increasing by length 1 every time. Again this reduces constant reallocation. -Use the has-child-nodes function instead of comparing length everywhere. I attached some test results I got (kind of long), here are the summary lines: seconds | consed | calls | sec/call | name ---------------------------------------------------------- 2.092 | 32,227,920 | 708,718 | | Total ;;OLD 0.859 | 25,507,240 | 691,366 | | Total ;;NEW

2 1

[cxml-devel] characters.lisp improvements
by Nathan Bird 13 Jun '06

13 Jun '06

Doing some profiling I found a good portion of time and memory was being spent in rune-in-range-p among others. Investigating the source I found a comment in german that google translates into something like "that can be done nevertheless better". So I did. We now use a binary search instead of a linear search. Type declarations (simple-vector) helped a bit on sbcl. As well as rune-name-char-p had been calling rune-in-range-p with each of a bunch of different lists. So I combined these lists at compile time, and search through the sorted list once. Some tests I did (each one twice): ;;ORGINAL seconds | consed | calls | sec/call | name -------------------------------------------------------- 0.075 | 1,266,472 | 43,752 | 0.000002 | RUNE-IN-RANGE-P 0.010 | 804,632 | 34,574 | 0.0000003 | RUNE-NAME-CHAR-P 0.000 | 1,018,912 | 4,670 | 0.000000 | VALID-NAME-P -------------------------------------------------------- 0.085 | 3,090,016 | 82,996 | | Total seconds | consed | calls | sec/call | name -------------------------------------------------------- 0.067 | 1,222,936 | 43,752 | 0.000002 | RUNE-IN-RANGE-P 0.003 | 1,078,888 | 34,574 | 0.0000001 | RUNE-NAME-CHAR-P 0.000 | 1,036,544 | 4,670 | 0.000000 | VALID-NAME-P -------------------------------------------------------- 0.070 | 3,338,368 | 82,996 | | Total ;;NEW seconds | consed | calls | sec/call | name -------------------------------------------------------- 0.043 | 0 | 37,001 | 0.000001 | RUNE-IN-RANGE-P 0.000 | 833,704 | 34,574 | 0.000000 | RUNE-NAME-CHAR-P 0.000 | 1,056,296 | 4,670 | 0.000000 | VALID-NAME-P -------------------------------------------------------- 0.043 | 1,890,000 | 76,245 | | Total seconds | consed | calls | sec/call | name -------------------------------------------------------- 0.028 | 0 | 37,001 | 0.000001 | RUNE-IN-RANGE-P 0.000 | 808,528 | 34,574 | 0.000000 | RUNE-NAME-CHAR-P 0.000 | 1,116,776 | 4,670 | 0.000000 | VALID-NAME-P -------------------------------------------------------- 0.028 | 1,925,304 | 76,245 | | Total Nathan Bird

2 1

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

cxml-devel June 2006