On Wed, 14 Dec 2016 17:19:27 -0800 Paul Eggert <egg...@cs.ucla.edu> wrote:
> I was referring to code with his proposed patch installed. 'delete' is > O(N); 'replace' calls 'delete' in a loop and is therefore O(N**2). > 'epsclosure' calls 'replace' in a loop and so I suppose it is O(N**3). > I haven't looked into how likely the worst-case performance is, though. Yes. It is same both before and after with my proposed patch, but It seems that memset() for VISITED causes slowdown in before code. So it may extremely depress efficiency of memory cache, although there is no basis. - before $ time -p env LC_ALL=C src/grep -F -w -f /usr/share/dict/linux.words /dev/null real 188.98 user 188.46 sys 0.33 - after $ time -p env LC_ALL=C src/grep -F -w -f /usr/share/dict/linux.words /dev/null real 2.19 user 1.84 sys 0.34