[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
bug#22357: grep -f not only huge memory usage, but also huge time cost
From: |
Norihiro Tanaka |
Subject: |
bug#22357: grep -f not only huge memory usage, but also huge time cost |
Date: |
Sun, 18 Dec 2016 10:30:13 +0900 |
On Wed, 14 Dec 2016 17:19:27 -0800
Paul Eggert <address@hidden> 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
- bug#22357: grep -f not only huge memory usage, but also huge time cost, Trevor Cordes, 2016/12/09
- bug#22357: grep -f not only huge memory usage, but also huge time cost, Norihiro Tanaka, 2016/12/10
- bug#22357: grep -f not only huge memory usage, but also huge time cost, Trevor Cordes, 2016/12/11
- bug#22357: grep -f not only huge memory usage, but also huge time cost, Norihiro Tanaka, 2016/12/11
- bug#22357: grep -f not only huge memory usage, but also huge time cost, Bruno Haible, 2016/12/11
- bug#22357: grep -f not only huge memory usage, but also huge time cost, arnold, 2016/12/11
- bug#22357: grep -f not only huge memory usage, but also huge time cost, Paul Eggert, 2016/12/11
- bug#22357: grep -f not only huge memory usage, but also huge time cost, Bruno Haible, 2016/12/12
- bug#22357: grep -f not only huge memory usage, but also huge time cost, Paul Eggert, 2016/12/14
- bug#22357: grep -f not only huge memory usage, but also huge time cost,
Norihiro Tanaka <=
- bug#22357: grep -f not only huge memory usage, but also huge time cost, Paul Eggert, 2016/12/19
- bug#22357: grep -f not only huge memory usage, but also huge time cost, Norihiro Tanaka, 2016/12/19
- bug#22357: grep -f not only huge memory usage, but also huge time cost, Paul Eggert, 2016/12/19
- bug#22357: grep -f not only huge memory usage, but also huge time cost, Norihiro Tanaka, 2016/12/20
- bug#22357: grep -f not only huge memory usage, but also huge time cost, Norihiro Tanaka, 2016/12/12
- bug#22357: grep -f not only huge memory usage, but also huge time cost, Trevor Cordes, 2016/12/12
- bug#22357: grep -f not only huge memory usage, but also huge time cost, Paul Eggert, 2016/12/12
- bug#22357: grep -f not only huge memory usage, but also huge time cost, Trevor Cordes, 2016/12/12
- bug#22357: grep -f not only huge memory usage, but also huge time cost, Paul Eggert, 2016/12/12
- bug#22357: grep -f not only huge memory usage, but also huge time cost, L.A. Walsh, 2016/12/15