I rewrote my parsing code in C/C++ and a task that was likely to take two years in Groovy/Java while running 18 threads – on a multicore machine with a large amount of memory – (I am not exaggerating about the turnaround time, either) completed in not much more than three hours in a single thread on the same machine.
(The new code has a C main – but the bulk of the code is in C++ which is accessed through an extern “C” interface.)
#include <iostream> #include <cstdio> #include "redblack.hpp" using namespace std; //Copyright Adrian McMenamin 2014 //acm538@york.ac.uk //C wrap around C++ redblack tree code //Licensed under GNU GPL verison 2 //or any later version at your discretion class pageinst { private: long instruction; pageinst* next; public: pageinst(long inst); long getinst(void); pageinst* getnext(void); void setnext(pageinst* newinst); }; pageinst::pageinst(long inst) { instruction = inst; next = NULL; } long pageinst::getinst(void) { return instruction; } pageinst* pageinst::getnext(void) { return next; } void pageinst::setnext(pageinst* newinst) { next = newinst; } class pagechain { friend ostream& operator<<(ostream& os, pagechain& pc); private: long page; pageinst* head; pageinst* tail; public: pagechain(long where); long getpage(void); bool operator==(pagechain&) const; bool operator<(pagechain&) const; pageinst* gethead(void); void sethead(pageinst* newhead); pageinst* gettail(void); void settail(pageinst* newtail); }; ostream& operator<<(ostream& os, pagechain& pc) { os << pc.page; return os; } long pagechain::getpage(void) { return page; } bool pagechain::operator==(pagechain& pc) const { return (page == pc.page); } bool pagechain::operator<(pagechain& pc) const { return (page < pc.page); } pagechain::pagechain(long where) { page = where; head = NULL; tail = NULL; } pageinst* pagechain::gethead(void) { return head; } void pagechain::sethead(pageinst* newhead) { pageinst* oldhead = gethead(); head = newhead; if (oldhead) newhead->setnext(oldhead); if (!gettail()) tail = newhead; } pageinst* pagechain::gettail(void) { return tail; } void pagechain::settail(pageinst* newtail) { pageinst* oldtail = gettail(); tail = newtail; if (oldtail) oldtail->setnext(newtail); if (!gethead()) head = newtail; } void killchain(pageinst* pi) { if (pi == NULL) return; pageinst* next = pi->getnext(); delete pi; killchain(next); } void killtree(redblacknode<pagechain>* node) { if (node == NULL) return; killtree(node->left); killtree(node->right); killchain(node->getvalue().gethead()); } void writechain(pagechain* pc, FILE* fout) { if (pc == NULL) return; fprintf(fout, "PAGE: %li ", pc->getpage()); pageinst* pi = pc->gethead(); while (pi) { fprintf(fout, ",%li", pi->getinst()); pi = pi->getnext(); } fprintf(fout, "\n"); } void writeoutpages(redblacknode<pagechain>* node, FILE* fout) { if (node == NULL) return; writeoutpages(node->left, fout); writechain(&node->getvalue(), fout); writeoutpages(node->right, fout); } extern "C" { void* createtree(void) { redblacktree<redblacknode<pagechain> >* tree; tree = new redblacktree<redblacknode<pagechain> >(); return static_cast<void*>(tree); } void removetree(void* tree) { redblacktree<redblacknode >* rbtree; rbtree = (static_cast<redblacktree<redblacknode<pagechain> >* >(tree)); killtree(rbtree->root); delete rbtree; tree = NULL; } void* getroot(void* tree) { redblacktree<redblacknode<pagechain> >* nodetree = static_cast<redblacktree<redblacknode<pagechain> >*>(tree); return static_cast<void*>(nodetree->root); } //if node for this page exists add to its tail //if node for this page does not exist, create and add to tail void insertinstruction(long pagenumber, long instruction, void* tree, void* root) { redblacknode<pagechain> *rootnode, *pagenode, *dummynode; redblacktree<redblacknode<pagechain> >* nodetree; pagechain dummychain = pagechain(pagenumber); rootnode = static_cast<redblacknode<pagechain>*>(root); nodetree = static_cast<redblacktree<redblacknode<pagechain> >* >(tree); dummynode = new redblacknode<pagechain>(dummychain); pagenode = nodetree->locatenode(dummynode, rootnode); pageinst* nextinstruction = new pageinst(instruction); if (pagenode) { pagenode->getvalue().settail(nextinstruction); delete dummynode; } else { dummynode->getvalue().settail(nextinstruction); nodetree->insertnode(dummynode, rootnode); } } void writeinorder(void* tree, FILE* fileout) { redblacktree<redblacknode<pagechain> >* nodetree = static_cast<redblacktree<redblacknode<pagechain> >*> (tree); writeoutpages(nodetree->root, fileout); } } //end extern "C"
The old code used Groovy’s Map class to index a sparse array, the new code uses a red-black tree to index the same data. The speed up is not just because of the tree’s superior performance, but it surely has a lot to do with it.
I now have to decide whether to re-write the whole of the testing code in C/C++ … I think I am going to have to.