D-Programming-Language/phobos — pull request #983 by monarchdodra (2012-11-30 16:31:31+00:00)
Title: split improvments: Both performance and unicode.

This is a pull that improves splitWhite: It allows it to split unicode, and improves performance.

# The commits:
1. https://github.com/monarchdodra/phobos/commit/32dafbfe71b609ce065df7ec6ffe8f38bdf9f5f3 Improve std.uni.isWhite by first checking if c < 0x80, and then branching to 1 of two implementation. This *greatly* improves the speed of `std.uni.isWhite` for *all* ascii characters, for *all* programs.
2. https://github.com/monarchdodra/phobos/commit/80155a6c00a569c63f50bfc6aaffde4cf99f9728 Use appender in split. Makes it faster as early as the second token.
3. https://github.com/monarchdodra/phobos/commit/86083860785bca91461bf8c777e0bff70b2a3bc1 Use std.ascii.isWhite in split. Just a step before making it unicode.
4. https://github.com/monarchdodra/phobos/commit/f32698c007a6a5da2363a2b26d69da85d79cd617 Making split it unicode.
5. https://github.com/monarchdodra/phobos/commit/3738f048059aecc4f833200ef66a031e4f71217f Unittest
6. https://github.com/monarchdodra/phobos/commit/3c684c4b4600164a5e40c5ee136bc72987d1023e New implementation for split. Faster as a whole.
7. https://github.com/monarchdodra/phobos/commit/d69368e101995256024d167e999165ddc2491b87 Introducing the (internal) function decodeIsWhite: It does both operations at once, giving a good boost to performance.
8. https://github.com/monarchdodra/phobos/commit/0d63710e776845c764ba560f42791626bc27c2dd decodeIsWhite unittests
9. https://github.com/monarchdodra/phobos/commit/1406bcbc009956fed8f69a3b83b7a6c14e74da70 Deploying it in decodeIsWhite stripLeft
10. https://github.com/monarchdodra/phobos/commit/1191d9c3c868cf1f61bdd7007d5a00a73864fdc7 Deploying decodeIsWhite in decodeIsWhite split
11. https://github.com/monarchdodra/phobos/commit/98314b354d28f1b4a3431767451ac8eef079bf0f More aggressive implementation of decodeIsWhite
12. https://github.com/monarchdodra/phobos/commit/7946aa40d75eb38e6257b88bbbbfeb6e427d9f7e dchar specialization for split

I'll probably rebase a bit when the review is done.

# The test methods.
There are 10 players:
1. C1: The original "classic" split
2. C2: The same with Appender
3. C3: Using std.ascii.isWhite
3. C4: Using std.uni.isWhite
4. CD1: The classic implementation, using a "decode" approach (for comparison)
5. CD2: Ditto, but uses the first decodeIsWhite
6. CD3: Ditto, but uses the second decodeIsWhite
7. D1: My new decode based implementation
8. D2: Ditto, but uses the second decodeIsWhite
9. D2: Ditto, but uses the first decodeIsWhite
10. DD: A specialized dchar implementation

And the input data, in two groups.

Short strings.
```
1. "white1" : ""
2. "white2" : " "
3. "Hello" : "Hello"
4. "HW" : "Hello World"
5. "HBBW" : " hello big beautiful world ",
6. "NHG" : "　日　本　語　"
```
Long strings.
7. "LI" : Lorem ipsum poem
8. "Blackburn" : Wikipedia's html of the page "Blackburn"
9. "Japanese" : Wikipedia's html of the page "Japanese"
10. "Nihongo" : Wikipedia.jp's html of the page "Nihongo"
11. "Chinese" : An excerpt of "Ulysses" in chinese (http://www.humancomp.org/unichtm/ulysses8.htm)
12. "Mongolian" : The source of "http://mk.wikipedia.org/wiki/%D0%9C%D0%BE%D0%BD%D0%B3%D0%BE%D0%BB%D1%81%D0%BA%D0%B8_%D1%98%D0%B0%D0%B7%D0%B8%D0%BA"
13. "Zenbibl8" : a bibliography on "CHAN / ZEN / SON BUDDHISM (1977-1992)" (http://www.humancomp.org/unichtm/zenbibl8.htl)

Each piece of data is parsed (in random order), and then split repeatedly. Each test last about 5 seconds before moving on to the next
The tests where run 10 times.

# Benches
The first table is the raw times. The second, is the time in percentage, relative to the CD1 run of the same string.

Note that ALL these tests take into account my first `isWhite` improvement.

ALSO: SCROLL RIGHT TO SEE THE LONG STRING TIMES

white1	white2	Hello	HW	HBBW	NHG	LI	Blackburn	Japanese	Nihongo	Chinese	Mongolian	Zenbibl8

C1	276	581	15732	30599	26312	8940	24963	11889	11344	18225	8487	6491	28116

C2	9161	9297	22474	23150	20836	11579	12296	6557	6703	12917	6812	3910	14978

C3	9159	9742	23439	24943	25384	12318	16109	10277	10352	21044	9491	6362	20336

C4	9436	10681	24640	28646	29209	24699	23021	15989	15818	37572	21161	11736	31902

CD1	9240	10299	24700	27161	29144	23760	20604	13720	13742	31479	17626	9458	28188

CD2	9230	10169	24172	26471	26652	22403	18171	11364	11409	26961	16453	7845	25223

CD3	9369	9975	24465	25940	26181	19007	17868	11546	11495	24910	9964	7266	23648

D1	759	2032	24068	27877	26645	22999	19673	12728	12844	29456	16437	8885	26596

D2	751	2039	25194	27330	24910	22512	17764	10783	10963	26110	15681	7642	24117

D3	757	2030	22741	28990	25382	20533	17668	10896	10976	23782	9327	7001	22727

white1	white2	Hello	HW	HBBW	NHG	LI	Blackburn	Japanese	Nihongo	Chinese	Mongolian	Zenbibl8

C1	314	664	34595	43943	34846	8933	40180	14071	13487	17363	4828	6983	30061

C2	11647	11870	27977	32578	27446	12401	22440	8574	8526	12207	3595	4418	16952

C3	11638	12357	28763	33628	31015	12286	26035	12061	11977	18705	4585	6505	21717

C4	11976	13230	30239	37018	35837	26990	32633	17218	16985	33342	13980	11165	32533

CD1	12610	13877	31227	38242	36360	25790	32635	17436	17131	31322	12015	10572	32028

CD2	11640	12740	29183	36256	34853	25665	30448	15166	14988	27250	10249	9239	28996

CD3	11635	12730	29367	36426	33798	25234	30435	15054	14841	26859	10158	9082	28459

D1	702	2017	31496	38070	33367	26212	31722	16424	16146	29728	11222	9900	30321

D2	705	2016	30276	38008	32687	25735	29920	14887	14662	26854	9803	9130	28543

D3	707	2014	28379	39396	32119	25503	29363	14427	14212	25701	9589	8635	27443

white1	white2	Hello	HW	HBBW	NHG	LI	Blackburn	Japanese	Nihongo	Chinese	Mongolian	Zenbibl8

C1	253	579	23423	42354	38555	9293	48346	12491	11704	15440	4100	6402	28908

C2	13433	13582	37773	30727	30788	13959	27824	7718	6902	10406	2897	3902	16241

C3	13373	13981	38644	33344	35157	14171	31677	11592	10650	18040	4370	6403	21123

C4	13277	14030	38825	34303	35055	28824	31737	11527	10660	19947	6993	6889	21843

CD1	13360	14289	38659	34416	37499	29300	35572	14201	13258	24995	9759	8502	27371

CD2	13380	14355	39450	34439	37544	29590	35298	14123	13215	24759	9174	8511	26969

CD3	13349	14202	38133	38536	38268	30330	34289	13032	12151	22689	8025	7864	25075

D1	566	1201	45246	38033	35802	29205	34964	13998	12890	24515	9239	8334	26443

D2	570	1193	33129	43180	36377	29947	34978	13484	12447	23544	8720	8017	26147

D3	564	1189	31797	46063	37140	30352	33870	12746	11778	22286	7664	7741	24128

DD	507	1117	29373	41209	32814	28484	30333	9925	9142	16931	5963	5895	19925

white1	white2	Hello	HW	HBBW	NHG	LI	Blackburn	Japanese	Nihongo	Chinese	Mongolian	Zenbibl8

C1	3%	6%	64%	113%	90%	38%	121%	87%	83%	58%	48%	69%	100%

C2	99%	90%	91%	85%	71%	49%	60%	48%	49%	41%	39%	41%	53%

C3	99%	95%	95%	92%	87%	52%	78%	75%	75%	67%	54%	67%	72%

C4	102%	104%	100%	105%	100%	104%	112%	117%	115%	119%	120%	124%	113%

CD1	100%	100%	100%	100%	100%	100%	100%	100%	100%	100%	100%	100%	100%

CD2	100%	99%	98%	97%	91%	94%	88%	83%	83%	86%	93%	83%	89%

CD3	101%	97%	99%	96%	90%	80%	87%	84%	84%	79%	57%	77%	84%

D1	8%	20%	97%	103%	91%	97%	95%	93%	93%	94%	93%	94%	94%

D2	8%	20%	102%	101%	85%	95%	86%	79%	80%	83%	89%	81%	86%

D3	8%	20%	92%	107%	87%	86%	86%	79%	80%	76%	53%	74%	81%

white1	white2	Hello	HW	HBBW	NHG	LI	Blackburn	Japanese	Nihongo	Chinese	Mongolian	Zenbibl8

C1	2%	5%	111%	115%	96%	35%	123%	81%	79%	55%	40%	66%	94%

C2	92%	86%	90%	85%	75%	48%	69%	49%	50%	39%	30%	42%	53%

C3	92%	89%	92%	88%	85%	48%	80%	69%	70%	60%	38%	62%	68%

C4	95%	95%	97%	97%	99%	105%	100%	99%	99%	106%	116%	106%	102%

CD1	100%	100%	100%	100%	100%	100%	100%	100%	100%	100%	100%	100%	100%

CD2	92%	92%	93%	95%	96%	100%	93%	87%	87%	87%	85%	87%	91%

CD3	92%	92%	94%	95%	93%	98%	93%	86%	87%	86%	85%	86%	89%

D1	6%	15%	101%	100%	92%	102%	97%	94%	94%	95%	93%	94%	95%

D2	6%	15%	97%	99%	90%	100%	92%	85%	86%	86%	82%	86%	89%

D3	6%	15%	91%	103%	88%	99%	90%	83%	83%	82%	80%	82%	86%

white1	white2	Hello	HW	HBBW	NHG	LI	Blackburn	Japanese	Nihongo	Chinese	Mongolian	Zenbibl8

C1	2%	4%	61%	123%	103%	32%	136%	88%	88%	62%	42%	75%	106%

C2	101%	95%	98%	89%	82%	48%	78%	54%	52%	42%	30%	46%	59%

C3	100%	98%	100%	97%	94%	48%	89%	82%	80%	72%	45%	75%	77%

C4	99%	98%	100%	100%	93%	98%	89%	81%	80%	80%	72%	81%	80%

CD1	100%	100%	100%	100%	100%	100%	100%	100%	100%	100%	100%	100%	100%

CD2	100%	100%	102%	100%	100%	101%	99%	99%	100%	99%	94%	100%	99%

CD3	100%	99%	99%	112%	102%	104%	96%	92%	92%	91%	82%	92%	92%

D1	4%	8%	117%	111%	95%	100%	98%	99%	97%	98%	95%	98%	97%

D2	4%	8%	86%	125%	97%	102%	98%	95%	94%	94%	89%	94%	96%

D3	4%	8%	82%	134%	99%	104%	95%	90%	89%	89%	79%	91%	88%

DD	4%	8%	76%	120%	88%	97%	85%	70%	69%	68%	61%	69%	73%

# Interpretation

The first thing we see is that splitting on unicode is *NOT* cheap. However, each successive implementation speeds up the parsing. The final result is that my proposed unicode split is just as fast as the current ASCII split. Of course, it also means there is less room for improvement now...

The actual improvements, of course, depend on how heavilly the string relies on unicode: The Chinese Ulysses test has a 100% speed improvement over a simple decode though (!)

UTF-8 has the most gains, with consistent gains, and few deviation of results.
UTF-16 and UTF-32 has less consistent improvements, and more deviations from one test to the next. Still, they also gain for the changes.

We can see though that using decode for dchars is not a good idea, so I also provided my implementation in a basic loop pattern for dchars.

# Conclusion

There is, of course, a "amount of new code" vs "performance gain" tradeof. I am more than willing to remove/tame certain aspects of my code. Still, this is the full studdy of what I've been doing for the past 3 weeks, so I wanted to present it in its full form.