/*
**********************************************************************
* Copyright (C) 2010-2014, International Business Machines
* Corporation and others. All Rights Reserved.
**********************************************************************
* file name: dicttrieperf.cpp
* encoding: US-ASCII
* tab size: 8 (not used)
* indentation:4
*
* created on: 2010dec09
* created by: Markus W. Scherer
*
* Performance test program for dictionary-type tries.
*
* Usage from within <ICU build tree>/test/perf/dicttrieperf/ :
* (Linux)
* make
* export LD_LIBRARY_PATH=../../../lib:../../../stubdata:../../../tools/ctestfw
* ./dicttrieperf --sourcedir <ICU build tree>/data/out/tmp --passes 3 --iterations 1000
* or
* ./dicttrieperf -f <ICU source tree>/source/data/brkitr/thaidict.txt --passes 3 --iterations 250
*/
#include <stdio.h>
#include <stdlib.h>
#include "unicode/bytestrie.h"
#include "unicode/bytestriebuilder.h"
#include "unicode/localpointer.h"
#include "unicode/ucharstrie.h"
#include "unicode/ucharstriebuilder.h"
#include "unicode/uperf.h"
#include "unicode/utext.h"
#include "charstr.h"
#include "package.h"
#include "toolutil.h"
#include "ucbuf.h" // struct ULine
#include "uoptions.h"
#include "uvectr32.h"
#include "cmemory.h" // for UPRV_LENGTHOF
// Test object.
class DictionaryTriePerfTest : public UPerfTest {
public:
DictionaryTriePerfTest(int32_t argc, const char *argv[], UErrorCode &status)
: UPerfTest(argc, argv, NULL, 0, "", status), numTextLines(0) {
if(hasFile()) {
getLines(status);
for(int32_t i=0; i<numLines; ++i) {
// Skip comment lines (start with a character below 'A').
if(lines[i].name[0]>=0x41) {
++numTextLines;
// Remove trailing CR LF.
int32_t len=lines[i].len;
UChar c;
while(len>0 && ((c=lines[i].name[len-1])==0xa || c==0xd)) {
--len;
}
lines[i].len=len;
}
}
}
}
virtual UPerfFunction *runIndexedTest(int32_t index, UBool exec, const char *&name, char *par=NULL);
const char *getSourceDir() const { return sourceDir; }
UBool hasFile() const { return ucharBuf!=NULL; }
const ULine *getCachedLines() const { return lines; }
int32_t getNumLines() const { return numLines; }
int32_t numTextLines; // excluding comment lines
};
// Performance test function object.
// Loads icudt46l.dat (or whatever its current versioned filename)
// from the -s or --sourcedir path.
class PackageLookup : public UPerfFunction {
protected:
PackageLookup(const DictionaryTriePerfTest &perf) {
IcuToolErrorCode errorCode("PackageLookup()");
CharString filename(perf.getSourceDir(), errorCode);
int32_t filenameLength=filename.length();
if(filenameLength>0 && filename[filenameLength-1]!=U_FILE_SEP_CHAR &&
filename[filenameLength-1]!=U_FILE_ALT_SEP_CHAR) {
filename.append(U_FILE_SEP_CHAR, errorCode);
}
filename.append(U_ICUDATA_NAME, errorCode);
filename.append(".dat", errorCode);
pkg.readPackage(filename.data());
}
public:
virtual ~PackageLookup() {}
// virtual void call(UErrorCode* pErrorCode) { ... }
virtual long getOperationsPerIteration() {
return pkg.getItemCount();
}
// virtual long getEventsPerIteration();
protected:
Package pkg;
};
struct TOCEntry {
int32_t nameOffset, dataOffset;
};
// Similar to ICU 4.6 offsetTOCLookupFn() (in ucmndata.c).
static int32_t simpleBinarySearch(const char *s, const char *names, const TOCEntry *toc, int32_t count) {
int32_t start=0;
int32_t limit=count;
int32_t lastNumber=limit;
for(;;) {
int32_t number=(start+limit)/2;
if(lastNumber==number) { // have we moved?
return -1; // not found
}
lastNumber=number;
int32_t cmp=strcmp(s, names+toc[number].nameOffset);
if(cmp<0) {
limit=number;
} else if(cmp>0) {
start=number;
} else { // found s
return number;
}
}
}
class BinarySearchPackageLookup : public PackageLookup {
public:
BinarySearchPackageLookup(const DictionaryTriePerfTest &perf)
: PackageLookup(perf) {
IcuToolErrorCode errorCode("BinarySearchPackageLookup()");
int32_t count=pkg.getItemCount();
toc=new TOCEntry[count];
for(int32_t i=0; i<count; ++i) {
toc[i].nameOffset=itemNames.length();
toc[i].dataOffset=i; // arbitrary value, see toc comment below
// The Package class removes the "icudt46l/" prefix.
// We restore that here for a fair performance test.
const char *name=pkg.getItem(i)->name;
itemNames.append("icudt46l/", errorCode);
itemNames.append(name, strlen(name)+1, errorCode);
}
printf("size of item names: %6ld\n", (long)itemNames.length());
printf("size of TOC: %6ld\n", (long)(count*8));
printf("total index size: %6ld\n", (long)(itemNames.length()+count*8));
}
virtual ~BinarySearchPackageLookup() {
delete[] toc;
}
virtual void call(UErrorCode * /*pErrorCode*/) {
int32_t count=pkg.getItemCount();
const char *itemNameChars=itemNames.data();
const char *name=itemNameChars;
for(int32_t i=0; i<count; ++i) {
if(simpleBinarySearch(name, itemNameChars, toc, count)<0) {
fprintf(stderr, "item not found: %s\n", name);
}
name=strchr(name, 0)+1;
}
}
protected:
CharString itemNames;
// toc imitates a .dat file's array of UDataOffsetTOCEntry
// with nameOffset and dataOffset.
// We don't need the dataOffsets, but we want to imitate the real
// memory density, to measure equivalent CPU cache usage.
TOCEntry *toc;
};
#ifndef MIN
#define MIN(a,b) (((a)<(b)) ? (a) : (b))
#endif
// Compare strings where we know the shared prefix length,
// and advance the prefix length as we find that the strings share even more characters.
static int32_t strcmpAfterPrefix(const char *s1, const char *s2, int32_t &prefixLength) {
int32_t pl=prefixLength;
s1+=pl;
s2+=pl;
int32_t cmp=0;
for(;;) {
int32_t c1=(uint8_t)*s1++;
int32_t c2=(uint8_t)*s2++;
cmp=c1-c2;
if(cmp!=0 || c1==0) { // different or done
break;
}
++pl; // increment shared same-prefix length
}
prefixLength=pl;
return cmp;
}
static int32_t prefixBinarySearch(const char *s, const char *names, const TOCEntry *toc, int32_t count) {
if(count==0) {
return -1;
}
int32_t start=0;
int32_t limit=count;
// Remember the shared prefix between s, start and limit,
// and don't compare that shared prefix again.
// The shared prefix should get longer as we narrow the [start, limit[ range.
int32_t startPrefixLength=0;
int32_t limitPrefixLength=0;
// Prime the prefix lengths so that we don't keep prefixLength at 0 until
// both the start and limit indexes have moved.
// At the same time, we find if s is one of the start and (limit-1) names,
// and if not, exclude them from the actual binary search.
if(0==strcmpAfterPrefix(s, names+toc[0].nameOffset, startPrefixLength)) {
return 0;
}
++start;
--limit;
if(0==strcmpAfterPrefix(s, names+toc[limit].nameOffset, limitPrefixLength)) {
return limit;
}
while(start<limit) {
int32_t i=(start+limit)/2;
int32_t prefixLength=MIN(startPrefixLength, limitPrefixLength);
int32_t cmp=strcmpAfterPrefix(s, names+toc[i].nameOffset, prefixLength);
if(cmp<0) {
limit=i;
limitPrefixLength=prefixLength;
} else if(cmp==0) {
return i;
} else {
start=i+1;
startPrefixLength=prefixLength;
}
}
return -1;
}
class PrefixBinarySearchPackageLookup : public BinarySearchPackageLookup {
public:
PrefixBinarySearchPackageLookup(const DictionaryTriePerfTest &perf)
: BinarySearchPackageLookup(perf) {}
virtual void call(UErrorCode * /*pErrorCode*/) {
int32_t count=pkg.getItemCount();
const char *itemNameChars=itemNames.data();
const char *name=itemNameChars;
for(int32_t i=0; i<count; ++i) {
if(prefixBinarySearch(name, itemNameChars, toc, count)<0) {
fprintf(stderr, "item not found: %s\n", name);
}
name=strchr(name, 0)+1;
}
}
};
static int32_t bytesTrieLookup(const char *s, const char *nameTrieBytes) {
BytesTrie trie(nameTrieBytes);
if(USTRINGTRIE_HAS_VALUE(trie.next(s, -1))) {
return trie.getValue();
} else {
return -1;
}
}
class BytesTriePackageLookup : public PackageLookup {
public:
BytesTriePackageLookup(const DictionaryTriePerfTest &perf)
: PackageLookup(perf) {
IcuToolErrorCode errorCode("BinarySearchPackageLookup()");
builder=new BytesTrieBuilder(errorCode);
int32_t count=pkg.getItemCount();
for(int32_t i=0; i<count; ++i) {
// The Package class removes the "icudt46l/" prefix.
// We restore that here for a fair performance test.
// We store all full names so that we do not have to reconstruct them
// in the call() function.
const char *name=pkg.getItem(i)->name;
int32_t offset=itemNames.length();
itemNames.append("icudt46l/", errorCode);
itemNames.append(name, -1, errorCode);
// As value, set the data item index.
// In a real implementation, we would use that to get the
// start and limit offset of the data item.
StringPiece fullName(itemNames.toStringPiece());
fullName.remove_prefix(offset);
builder->add(fullName, i, errorCode);
// NUL-terminate the name for call() to find the next one.
itemNames.append(0, errorCode);
}
int32_t length=builder->buildStringPiece(USTRINGTRIE_BUILD_SMALL, errorCode).length();
printf("size of BytesTrie: %6ld\n", (long)length);
// count+1: +1 for the last-item limit offset which we should have always had
printf("size of dataOffsets:%6ld\n", (long)((count+1)*4));
printf("total index size: %6ld\n", (long)(length+(count+1)*4));
}
virtual ~BytesTriePackageLookup() {
delete builder;
}
virtual void call(UErrorCode *pErrorCode) {
int32_t count=pkg.getItemCount();
const char *nameTrieBytes=builder->buildStringPiece(USTRINGTRIE_BUILD_SMALL, *pErrorCode).data();
const char *name=itemNames.data();
for(int32_t i=0; i<count; ++i) {
if(bytesTrieLookup(name, nameTrieBytes)<0) {
fprintf(stderr, "item not found: %s\n", name);
}
name=strchr(name, 0)+1;
}
}
protected:
BytesTrieBuilder *builder;
CharString itemNames;
};
// Performance test function object.
// Each subclass loads a dictionary text file
// from the -s or --sourcedir path plus -f or --file-name.
// For example, <ICU source dir>/source/data/brkitr/thaidict.txt.
class DictLookup : public UPerfFunction {
public:
DictLookup(const DictionaryTriePerfTest &perfTest) : perf(perfTest) {}
virtual long getOperationsPerIteration() {
return perf.numTextLines;
}
protected:
const DictionaryTriePerfTest &perf;
};
// Closely imitate CompactTrieDictionary::matches().
// Note: CompactTrieDictionary::matches() is part of its trie implementation,
// and while it loops over the text, it knows the current state.
// By contrast, this implementation uses UCharsTrie API functions that have to
// check the trie state each time and load/store state in the object.
// (Whether it hasNext() and whether it is in the middle of a linear-match node.)
static int32_t
ucharsTrieMatches(UCharsTrie &trie,
UText *text, int32_t textLimit,
int32_t *lengths, int &count, int limit ) {
UChar32 c=utext_next32(text);
// Notes:
// a) CompactTrieDictionary::matches() does not check for U_SENTINEL.
// b) It also ignores non-BMP code points by casting to UChar!
if(c<0) {
return 0;
}
// Should be firstForCodePoint() but CompactTrieDictionary
// handles only code units.
UStringTrieResult result=trie.first(c);
int32_t numChars=1;
count=0;
for(;;) {
if(USTRINGTRIE_HAS_VALUE(result)) {
if(count<limit) {
// lengths[count++]=(int32_t)utext_getNativeIndex(text);
lengths[count++]=numChars; // CompactTrieDictionary just counts chars too.
}
if(result==USTRINGTRIE_FINAL_VALUE) {
break;
}
} else if(result==USTRINGTRIE_NO_MATCH) {
break;
}
if(numChars>=textLimit) {
// Note: Why do we have both a text limit and a UText that knows its length?
break;
}
UChar32 c=utext_next32(text);
// Notes:
// a) CompactTrieDictionary::matches() does not check for U_SENTINEL.
// b) It also ignores non-BMP code points by casting to UChar!
if(c<0) {
break;
}
++numChars;
// Should be nextForCodePoint() but CompactTrieDictionary
// handles only code units.
result=trie.next(c);
}
#if 0
// Note: CompactTrieDictionary::matches() comments say that it leaves the UText
// after the longest prefix match and returns the number of characters
// that were matched.
if(index!=lastMatch) {
utext_setNativeIndex(text, lastMatch);
}
return lastMatch-start;
// However, it does not do either of these, so I am not trying to
// imitate it (or its docs) 100%.
#endif
return numChars;
}
class UCharsTrieDictLookup : public DictLookup {
public:
UCharsTrieDictLookup(const DictionaryTriePerfTest &perfTest)
: DictLookup(perfTest), trie(NULL) {
IcuToolErrorCode errorCode("UCharsTrieDictLookup()");
builder=new UCharsTrieBuilder(errorCode);
const ULine *lines=perf.getCachedLines();
int32_t numLines=perf.getNumLines();
for(int32_t i=0; i<numLines; ++i) {
// Skip comment lines (start with a character below 'A').
if(lines[i].name[0]<0x41) {
continue;
}
builder->add(UnicodeString(FALSE, lines[i].name, lines[i].len), 0, errorCode);
}
UnicodeString trieUChars;
int32_t length=builder->buildUnicodeString(USTRINGTRIE_BUILD_SMALL, trieUChars, errorCode).length();
printf("size of UCharsTrie: %6ld bytes\n", (long)length*2);
trie=builder->build(USTRINGTRIE_BUILD_SMALL, errorCode);
}
virtual ~UCharsTrieDictLookup() {
delete builder;
delete trie;
}
protected:
UCharsTrieBuilder *builder;
UCharsTrie *trie;
};
class UCharsTrieDictMatches : public UCharsTrieDictLookup {
public:
UCharsTrieDictMatches(const DictionaryTriePerfTest &perfTest)
: UCharsTrieDictLookup(perfTest) {}
virtual void call(UErrorCode *pErrorCode) {
UText text=UTEXT_INITIALIZER;
int32_t lengths[20];
const ULine *lines=perf.getCachedLines();
int32_t numLines=perf.getNumLines();
for(int32_t i=0; i<numLines; ++i) {
// Skip comment lines (start with a character below 'A').
if(lines[i].name[0]<0x41) {
continue;
}
utext_openUChars(&text, lines[i].name, lines[i].len, pErrorCode);
int32_t count=0;
ucharsTrieMatches(*trie, &text, lines[i].len,
lengths, count, UPRV_LENGTHOF(lengths));
if(count==0 || lengths[count-1]!=lines[i].len) {
fprintf(stderr, "word %ld (0-based) not found\n", (long)i);
}
}
}
};
class UCharsTrieDictContains : public UCharsTrieDictLookup {
public:
UCharsTrieDictContains(const DictionaryTriePerfTest &perfTest)
: UCharsTrieDictLookup(perfTest) {}
virtual void call(UErrorCode * /*pErrorCode*/) {
const ULine *lines=perf.getCachedLines();
int32_t numLines=perf.getNumLines();
for(int32_t i=0; i<numLines; ++i) {
// Skip comment lines (which start with a character below 'A').
if(lines[i].name[0]<0x41) {
continue;
}
if(!USTRINGTRIE_HAS_VALUE(trie->reset().next(lines[i].name, lines[i].len))) {
fprintf(stderr, "word %ld (0-based) not found\n", (long)i);
}
}
}
};
static inline int32_t thaiCharToByte(UChar32 c) {
if(0xe00<=c && c<=0xefe) {
return c&0xff;
} else if(c==0x2e) {
return 0xff;
} else {
return -1;
}
}
static UBool thaiWordToBytes(const UChar *s, int32_t length,
CharString &str, UErrorCode &errorCode) {
for(int32_t i=0; i<length; ++i) {
UChar c=s[i];
int32_t b=thaiCharToByte(c);
if(b>=0) {
str.append((char)b, errorCode);
} else {
fprintf(stderr, "thaiWordToBytes(): unable to encode U+%04X as a byte\n", c);
return FALSE;
}
}
return TRUE;
}
class BytesTrieDictLookup : public DictLookup {
public:
BytesTrieDictLookup(const DictionaryTriePerfTest &perfTest)
: DictLookup(perfTest), trie(NULL), noDict(FALSE) {
IcuToolErrorCode errorCode("BytesTrieDictLookup()");
builder=new BytesTrieBuilder(errorCode);
CharString str;
const ULine *lines=perf.getCachedLines();
int32_t numLines=perf.getNumLines();
for(int32_t i=0; i<numLines; ++i) {
// Skip comment lines (start with a character below 'A').
if(lines[i].name[0]<0x41) {
continue;
}
if(!thaiWordToBytes(lines[i].name, lines[i].len, str.clear(), errorCode)) {
fprintf(stderr, "thaiWordToBytes(): failed for word %ld (0-based)\n", (long)i);
noDict=TRUE;
break;
}
builder->add(str.toStringPiece(), 0, errorCode);
}
if(!noDict) {
int32_t length=builder->buildStringPiece(USTRINGTRIE_BUILD_SMALL, errorCode).length();
printf("size of BytesTrie: %6ld bytes\n", (long)length);
trie=builder->build(USTRINGTRIE_BUILD_SMALL, errorCode);
}
}
virtual ~BytesTrieDictLookup() {
delete builder;
delete trie;
}
protected:
BytesTrieBuilder *builder;
BytesTrie *trie;
UBool noDict;
};
static int32_t
bytesTrieMatches(BytesTrie &trie,
UText *text, int32_t textLimit,
int32_t *lengths, int &count, int limit ) {
UChar32 c=utext_next32(text);
if(c<0) {
return 0;
}
UStringTrieResult result=trie.first(thaiCharToByte(c));
int32_t numChars=1;
count=0;
for(;;) {
if(USTRINGTRIE_HAS_VALUE(result)) {
if(count<limit) {
// lengths[count++]=(int32_t)utext_getNativeIndex(text);
lengths[count++]=numChars; // CompactTrieDictionary just counts chars too.
}
if(result==USTRINGTRIE_FINAL_VALUE) {
break;
}
} else if(result==USTRINGTRIE_NO_MATCH) {
break;
}
if(numChars>=textLimit) {
break;
}
UChar32 c=utext_next32(text);
if(c<0) {
break;
}
++numChars;
result=trie.next(thaiCharToByte(c));
}
return numChars;
}
class BytesTrieDictMatches : public BytesTrieDictLookup {
public:
BytesTrieDictMatches(const DictionaryTriePerfTest &perfTest)
: BytesTrieDictLookup(perfTest) {}
virtual void call(UErrorCode *pErrorCode) {
if(noDict) {
return;
}
UText text=UTEXT_INITIALIZER;
int32_t lengths[20];
const ULine *lines=perf.getCachedLines();
int32_t numLines=perf.getNumLines();
for(int32_t i=0; i<numLines; ++i) {
// Skip comment lines (start with a character below 'A').
if(lines[i].name[0]<0x41) {
continue;
}
utext_openUChars(&text, lines[i].name, lines[i].len, pErrorCode);
int32_t count=0;
bytesTrieMatches(*trie, &text, lines[i].len,
lengths, count, UPRV_LENGTHOF(lengths));
if(count==0 || lengths[count-1]!=lines[i].len) {
fprintf(stderr, "word %ld (0-based) not found\n", (long)i);
}
}
}
};
class BytesTrieDictContains : public BytesTrieDictLookup {
public:
BytesTrieDictContains(const DictionaryTriePerfTest &perfTest)
: BytesTrieDictLookup(perfTest) {}
virtual void call(UErrorCode * /*pErrorCode*/) {
if(noDict) {
return;
}
const ULine *lines=perf.getCachedLines();
int32_t numLines=perf.getNumLines();
for(int32_t i=0; i<numLines; ++i) {
const UChar *line=lines[i].name;
// Skip comment lines (start with a character below 'A').
if(line[0]<0x41) {
continue;
}
UStringTrieResult result=trie->first(thaiCharToByte(line[0]));
int32_t lineLength=lines[i].len;
for(int32_t j=1; j<lineLength; ++j) {
if(!USTRINGTRIE_HAS_NEXT(result)) {
fprintf(stderr, "word %ld (0-based) not found\n", (long)i);
break;
}
result=trie->next(thaiCharToByte(line[j]));
}
if(!USTRINGTRIE_HAS_VALUE(result)) {
fprintf(stderr, "word %ld (0-based) not found\n", (long)i);
}
}
}
};
UPerfFunction *DictionaryTriePerfTest::runIndexedTest(int32_t index, UBool exec,
const char *&name, char * /*par*/) {
if(hasFile()) {
switch(index) {
case 0:
name="ucharstriematches";
if(exec) {
return new UCharsTrieDictMatches(*this);
}
break;
case 1:
name="ucharstriecontains";
if(exec) {
return new UCharsTrieDictContains(*this);
}
break;
case 2:
name="bytestriematches";
if(exec) {
return new BytesTrieDictMatches(*this);
}
break;
case 3:
name="bytestriecontains";
if(exec) {
return new BytesTrieDictContains(*this);
}
break;
default:
name="";
break;
}
} else {
if(index==0 && exec) {
puts("Running BytesTrie perf tests on the .dat package file from the --sourcedir.\n"
"For UCharsTrie perf tests on a dictionary text file, specify the -f or --file-name.\n");
}
switch(index) {
case 0:
name="simplebinarysearch";
if(exec) {
return new BinarySearchPackageLookup(*this);
}
break;
case 1:
name="prefixbinarysearch";
if(exec) {
return new PrefixBinarySearchPackageLookup(*this);
}
break;
case 2:
name="bytestrie";
if(exec) {
return new BytesTriePackageLookup(*this);
}
break;
default:
name="";
break;
}
}
return NULL;
}
int main(int argc, const char *argv[]) {
IcuToolErrorCode errorCode("dicttrieperf main()");
DictionaryTriePerfTest test(argc, argv, errorCode);
if(errorCode.isFailure()) {
fprintf(stderr, "DictionaryTriePerfTest() failed: %s\n", errorCode.errorName());
test.usage();
return errorCode.reset();
}
if(!test.run()) {
fprintf(stderr, "FAILED: Tests could not be run, please check the arguments.\n");
return -1;
}
return 0;
}