Needs a better dataset for comparison with large data size

[svanoort]

The full Hungarian wiki has ~4.3 GB of data, but ~2.5GB of unique string content:

cat data/huwiki-latest-pages-meta-current.xml | sed 's/[\t ]/\n/g' | grep -v ^$ | sort | uniq | wc -m

2507384541

There are ~25M unique tokens.

This means that we are generating gigantic hashtables with generally count = 1, and languages that store Unicode strings as 2-byte representations in memory suffer greatly due to memory overheads. Much of the memory used will simply be storing the unique strings.

[juditacs]

Word frequencies generally follow Zipf's law. About half of the tokens have count = 1 in a standard web corpora. Changing the dataset would not change the counts significantly.

[shssoichiro]

This is correct. I grabbed the full text of Harry Potter and the Deathly Hallows to verify this, and out of 25000 unique words, about 15000 had a count of 1, based on the definition of "word" in this benchmark (separated by breaking whitespace).

Removing characters such as quotation marks and commas would likely shift this ratio significantly, but that may add unneeded complexity to the benchmark task.

[juditacs]

Please don't call this a benchmark, I get nasty comments on the "internets" because of that. I don't have the resources nor the expertise to build an official benchmark.

If you read my first blog post, it's clear that this started as a homework-turned-fun-game. My colleagues were pretty excited and started to count words using their favourite language, so we built a test framework. 4 days ago less than 40 people knew about this and 35 of them were my friends.

[juditacs]

I've though about having a second round where whitespace characters would include Unicode whitespaces on but it takes a lot of time to manage this. It also wouldn't be fair since I know very well how to do this in Python and it's hard to be impartial.

[juditacs]

Can I close this?

[svanoort]

@shssoichiro My concern here is that many words are being treated as unique when they are not, because they have case changes or punctuation included. Zipf's law does suggest many one-use words, but the fact that the average 'word' is 100 characters is very dubious.

@juditacs I understand the pain you went through there, having suffered it myself (even after going through great pains to use a rigorous test methodology).

Please don't close this. I'm doing some analysis of datasets to see if there might be an easy way to tweak this to be a bit more representative.

I think Unicode whitespace characters are probably not worth worrying about, since they're likely to be rare (and are very numerous). Lowercasing all word characters and using the python character sets string.punctuation and string.whitespace as token separators (in addition to space, newline, and tab) is probably sufficient.

I will test this hypothesis and report back on results. My python 2/3/bash/java are strong enough to modify implementations appropriately if needed.

[juditacs]

This problem is called tokenization and it is far from trivial: https://en.wikipedia.org/wiki/Tokenization_%28lexical_analysis%29

Unicode whitespaces would be interesting to test the unicode support in each language not because the task itself makes much sense.

[svanoort]

My original results were slightly skewed by platform issues, I've got corrected numbers below.

Looking at the results here, I am now skeptical that the bash/GNU utils Unicode handling is correct in this case, because I see anomalously large numbers of Chinese characters (sometimes a symptom of Unicode being handled as raw bytes). I'm going to retry with Python variants.

Platform issue: when the analysis is run on Mac, the \n in the bash script silently converts to simple a 'n' character. This generates spurious results; I'd caution anyone doing testing to BE VERY CAUTIOUS about newline handling on different platforms.

In any cases, number of uniq tokens with punctuation and standard whitespace used as separators, running on Linux (Xubuntu 14.04):

cat data/huwiki-latest-pages-meta-current.xml | sed 's/[[:space:]|[:punct:]]+/\n/g' | grep -v ^$ | sort | uniq | wc -l

23566003 (23.5 million)

Number of unique characters:
cat data/huwiki-latest-pages-meta-current.xml | sed 's/[[:space:]|[:punct:]]+/\n/g' | grep -v ^$ | sort | uniq | wc -m

2507109596 (2.507 billion)

Uniq tokens with original criteria:
cat data/huwiki-latest-pages-meta-current.xml | sed 's/[\t ]+/\n/g' | grep -v ^$ | sort | uniq | wc -l

23531170 (also 23.5 million)

Uniq characters:

cat data/huwiki-latest-pages-meta-current.xml | sed 's/[\t ]+/\n/g' | grep -v ^$ | sort | uniq | wc -m

2507832256 (2.507 billion)

[svanoort]

@juditacs I think I have a solid solution for this, which yields a much better/more realistic corpus, but I wanted your thoughts before I cut a PR implementing it.

In general, it seems like this is one of the best large text corpuses so far (others are not large enough), but it is best handled by doing preprocessing to remove markup/formatting and leave more of the text content, and use the result as the benchmark corpus.

As an initial pass, here is a regex that will clean it up quite a bit by removing much of the irrelevant markup. It does this by removing some of the XML entity encoding, removing tag data (some of which is contained in entity-encoded markup), and replacing punctuation with spaces.

cat data/huwiki-latest-pages-meta-current.xml | sed 's/&gt;/>/g' | sed 's/&lt;/</g' | sed 's/&quot;/"/g' | sed 's/&amp;/&/g' | sed "s/&apos;/'/g" | sed -E 's/<[^>]+>//g' | sed -E 's/[[:space:]|[:punct:]]/ /g' | grep -v ^$ > data/cleaned-huwiki-latest-pages-meta-current.txt

It trims approximately 1 GB of markup/junk/entity-coding from the input XML corpus (reducing it to about 2.8 GB), but more importantly: total output size is reduced from 2.5 GB to 152 MB and unique token count is reduced to ~10.5 million, of which most seems to be actual word/token content.

If you approve, I will add this as a postprocessing step after unzipping the full wiki. It does take a few minutes to run. If we want to make parsers work harder, we could also replace the space/punctuation converter with something that yields an equal number of spaces. I can also add entity decoding for the ampersand and apostrophe characters too.

Search for binary embedded data: data:image/jpeg;base64 does not generate many lines, by the way.

Edit: benchmark comparison

Python 2 with original version, full wiki

real 4m30.933s
user 4m22.708s
sys 0m18.132s

Python 2 with cleaned up version, full wiki

real 2m57.748s
user 2m53.880s
sys 0m11.372s

The result of this is to put less benchmark emphasis on ensuring that binary data is stored in memory (not something like UTF-16), less emphasis on sorting, and far more emphasis on parsing performance and hashtable performance.

There are still 7M singleton tokens and 3 million multiple-instance tokens though, so it's a respectable benchmark of datastructures at-scale, and it also hits sort performance rather well.

[juditacs]

I really appreciate the effort you put into this. From an NLP perspective, the simple splitting and the lack of preprocessing would be unacceptable as tokenization. However, this task concentrates on IO and then on sorting, not tokenization. The output is of course unusable.

There are actually tools for textifying MediaWiki markup (Autocorpus). Real tokenization would require language-specific tools such as huntoken or NLTK with a Hungarian punctuation corpus, but that's not really the point here.

(If we want to decrease the amount of unique tokens (and therefore sorting), it would be enough to cut the corpus in half.)

[svanoort]

We both agree that the intent is not to generate truly useful NLP output, and that there are tools specificially for that purpose. My point is that some trivial preprocessing gives a far more useful result for comparing languages & implementations in this trivial testcase. It means you're performing an actual reduction on the data, and doing a sort operation with fairly normal sized strings.

The issue here is not the unique token count, but the fact that we're handing off oversized tokens that average 100 bytes per token, with little reduction of input data. The result is:

• An extremely large minimal working set in memory, relative to input data.
• Artificially heavy stress on (byte)string sorting performance with very long strings
• We also don't get to see the benefits of better dynamic memory management in the different languages, if much of the data stays permanently resident in memory once initially allocated.

Preprocessing simply achieves the goal of converting the data to stress the programming language in a more "natural" way.

To support my point, I used the simple space-based tokenizing rule on the following works (txt format ebooks)

• Stranger In a Strange Land (txt format), I get 248600 bytes of token content, out of 1184043 original characters, 29k tokens
• William Gibson's Mona Lisa Overdrive yields 126kB of token characters, out of 467518, with 15k tokens.
• The Illiad: 132k of token characters, out of 830k, 16k tokens. All of these are before any form of preprocessing, but using a plaintext (not XML, not WikiMarkup) format.

Now those token lengths are somewhat inflated by punctuation (otherwise words would be a more common 5-6 characters on average rather than tokens at 10ish).

[juditacs]

An extremely large minimal working set in memory, relative to input data.

This is true but necessary for stress testing. Otherwise we would need an even bigger input.

Artificially heavy stress on (byte)string sorting performance with very long strings

The whole experiment is artificial :)
The distribution of the tokens doesn't change with this kind of normalization and it doesn't need to.

We also don't get to see the benefits of better dynamic memory management in the different languages, if much of the data stays permanently resident in memory once initially allocated.

I don't see how a slightly cleaner dataset would change this.

I'll run a test on the normalized data.

[juditacs]

The converting ran for 17 minutes:

time cat data/huwiki-latest-pages-meta-current.xml | sed 's/>/>/g' | sed 's/<\/]+>//g' | sed -E 's/[[:space:]|[:punct:]]+/ /g' | grep -v ^$ > data/huwiki.clean

real    17m35.122s
user    19m46.661s
sys     1m11.562s

du -h data/*
3.2G    data/huwiki.clean
3.7G    data/huwiki-latest-pages-meta-current.xml
122M    data/huwikisource-latest-pages-meta-current.xml

It looks like about 7.5M lines from the clean data yield similar results to 5M from the old, but this of course need to be inspected:

# bash scripts/run_one.sh <(head -7500000 data/huwiki.clean ) rust/wordcount/wordcount
rust/wordcount/wordcount        18.22   17.43   1052624 
# bash scripts/run_one.sh <(head -5000000 data/huwiki-latest-pages-meta-current.xml ) rust/wordcount/wordcount
rust/wordcount/wordcount        17.74   17.06   990008  

[svanoort]

It would appear that markdown mangled the regex. I've appropriately escaped the code lines now, and am showing it runs in 6 minutes on my 4 year-old dual-core laptop (albeit one with an SSD).

Please try it with that in place, and run with the full corpus and not just the head 10%; the result should behave somewhat differently.

This is true but necessary for stress testing.

Not so much! We're still maxing out at least one CPU and stressing I/O, hitting memory allocation/deallocation and datastructures operations, plus sorting.

• 10.5M tokens (7M unique) is enough to require manipulating very large datastructures in memory, beyond normal cache sizes.
• We should still require at minimum several hundred MB of working set in memory (enough to stress memory use). However we will not absolutely require 3-8 GB of memory to run benchmarks, which means they can be run on lower-spec system.
• That last one I have plans for - to assist with this, I would like to set up a small, clean AWS environment that spins up on demand to run tests. However if it requires significant amounts of memory (or disk space to store outputs) then this becomes expensive.
• If we wanted to simply stress language behavior with a large working set in memory, this is not an appropriate way to do it because most of the allocated memory is only touched lightly

The distribution of the tokens doesn't change with this kind of normalization and it doesn't need to.

This is not true, please look at my numbers again, and with the corrected tokens. We went from 100B per token on average to about 10, and a ratio of unique:duplicate tokens that is much closer to a normal text body.

The whole experiment is artificial

Yes, but that does not mean it cannot be useful and cannot be improved! I think what we have here is something increasingly interesting and useful over time, and it will arrive at something more likely to draw praise than criticism.

Understand my point here is not to say that the existing setup is terrible, just that by doing preprocessing we make it more useful and representative in simulating real-world use cases. It also makes the game a bit more interesting than 'how quickly can you dump to RAM'?