dcache: faster dentry_cmp()
PATCH 1/1 dcache: faster dentry_cmp()
1) consistently use "unsigned int" for dentry name length,
2) reuse subtraction result for return value, exact value doesn't matter because function is only used in boolean context,
3) use *p++ idiom for even better code.
All of this results in performance speedup of "git diff" which is way out of statistical error (0.4% vs 0.15% of 3 sigma):
$ PAGER= perf stat -r 256 git-diff
Performance counter stats for 'git-diff' (256 runs):
115.033582 task-clock # 0.993 CPUs utilized ( +- 0.06% )
0 context-switches # 0.000 M/sec ( +- 17.95% )
0 CPU-migrations # 0.000 M/sec ( +- 19.47% )
2,321 page-faults # 0.020 M/sec ( +- 0.00% )
384,540,991 cycles # 3.343 GHz ( +- 0.05% )
121,833,562 stalled-cycles-frontend # 31.68% frontend cycles idle ( +- 0.16% )
51,731,784 stalled-cycles-backend # 13.45% backend cycles idle ( +- 0.37% )
586,327,441 instructions # 1.52 insns per cycle
# 0.21 stalled cycles per insn ( +- 0.00% )
155,449,246 branches # 1351.338 M/sec ( +- 0.00% )
542,511 branch-misses # 0.35% of all branches ( +- 0.07% )0.115856505 seconds time elapsed ( +- 0.06% )
----------------------------------
after
Performance counter stats for 'git-diff' (256 runs):
114.486145 task-clock # 0.993 CPUs utilized ( +- 0.05% )
0 context-switches # 0.000 M/sec ( +- 15.46% )
0 CPU-migrations # 0.000 M/sec ( +- 20.06% )
2,282 page-faults # 0.020 M/sec ( +- 0.00% )
382,725,382 cycles # 3.343 GHz ( +- 0.05% )
119,808,563 stalled-cycles-frontend # 31.30% frontend cycles idle ( +- 0.15% )
51,780,030 stalled-cycles-backend # 13.53% backend cycles idle ( +- 0.33% )
585,114,727 instructions # 1.53 insns per cycle
# 0.20 stalled cycles per insn ( +- 0.00% )
155,146,262 branches # 1355.153 M/sec ( +- 0.00% )
526,739 branch-misses # 0.34% of all branches ( +- 0.12% )0.115315823 seconds time elapsed ( +- 0.05% )
---
fs/dcache.c | 6 +++--- include/linux/dcache.h | 14 +++++++------- 2 files changed, 10 insertions(+), 10 deletions(-)
fs/dcache.c +3 -3
@@ -1368,7 +1368,7 @@ static struct dentry *__d_instantiate_unique(struct dentry *entry, struct inode *inode) {struct dentry *alias; -int len = entry->d_name.len; +unsigned int len = entry->d_name.len;const char *name = entry->d_name.name;unsigned int hash = entry->d_name.hash;
@@ -1750,7 +1750,7 @@ struct dentry *__d_lookup_rcu(struct dentry *parent, struct qstr *name,hlist_bl_for_each_entry_rcu (dentry, node, b, d_hash) {struct inode *i;const char *tname; -int tlen; +unsigned int tlen;if (dentry->d_name.hash != hash)continue ;
@@ -1869,7 +1869,7 @@ struct dentry *__d_lookup(struct dentry *parent, struct qstr *name)hlist_bl_for_each_entry_rcu (dentry, node, b, d_hash) {const char *tname; -int tlen; +unsigned int tlen;if (dentry->d_name.hash != hash)continue ;
include/linux/dcache.h +7 -7
@@ -51,18 +51,18 @@ extern struct dentry_stat_t dentry_stat;* Compare 2 name strings, return 0 if they match, otherwise non-zero. * The strings are both count bytes long, and count is non-zero. */ -static inline int dentry_cmp (const unsigned char *cs,size_t scount, -const unsigned char *ct,size_t tcount) +static inline int dentry_cmp (const unsigned char *cs,unsigned int scount, +const unsigned char *ct,unsigned int tcount) {int ret; -if (scount != tcount) -return 1 ; + + ret = scount - tcount; +if (ret) +return ret;do { - ret = (*cs != *ct); + ret = *cs++ - *ct++;if (ret)break ; - cs++; - ct++; tcount--; }while (tcount);return ret;
Al Viro
maintainerQuoted 14 lines · Alexey Dobriyan
1) consistently use "unsigned int" for dentry name length,
2) reuse subtraction result for return value, exact value doesn't matter because function is only used in boolean context,
3) use *p++ idiom for even better code.All of this results in performance speedup of "git diff" which is way out of statistical error (0.4% vs 0.15% of 3 sigma):
include/linux/dcache.h +4
-2-if (scount != tcount) -return 1 ; + + ret = scount - tcount; +if (ret) +return ret;
include/linux/dcache.h extern struct dentry_stat_t dentry_stat; · line 68
Quoted 10 lines
include/linux/dcache.h +1
-3do { - ret = (*cs != *ct); + ret = *cs++ - *ct++;if (ret)break ; - cs++; - ct++; tcount--; }while (tcount);return ret;
I wonder what'll happen if you simply replace that loop with
return memcmp(cs, ct, tcount);
which is what it really is...
Quoted 27 lines · Al Viro
Quoted 14 lines · Alexey Dobriyan
1) consistently use "unsigned int" for dentry name length,
2) reuse subtraction result for return value, exact value doesn't matter because function is only used in boolean context,
3) use *p++ idiom for even better code.All of this results in performance speedup of "git diff" which is way out of statistical error (0.4% vs 0.15% of 3 sigma):
include/linux/dcache.h +4
-2-if (scount != tcount) -return 1 ; + + ret = scount - tcount; +if (ret) +return ret;include/linux/dcache.h extern struct dentry_stat_t dentry_stat; · line 68
Quoted 10 lines
include/linux/dcache.h +1
-3do { - ret = (*cs != *ct); + ret = *cs++ - *ct++;if (ret)break ; - cs++; - ct++; tcount--; }while (tcount);return ret;I wonder what'll happen if you simply replace that loop with
Quoted 2 lines
return memcmp(cs, ct, tcount);which is what it really is...
It was memcmp() at some point and Nick changed it and it became faster. See 9d55c369bb5e695e629bc35cba2ef607755b3bee
"fs: implement faster dentry memcmp".
Quoted 4 lines · Alexey Dobriyan
1) consistently use "unsigned int" for dentry name length,
2) reuse subtraction result for return value, exact value doesn't matter because function is only used in boolean context,
3) use *p++ idiom for even better code.
I'm sure there are even better ways to do the comparision using longer words, especially as we know the boundaries and alignment.
-Andi
Signature · 1 line
[email protected] -- Speaking for myself only
Quoted 9 lines · Andi Kleen
Quoted 4 lines · Alexey Dobriyan
1) consistently use "unsigned int" for dentry name length,
2) reuse subtraction result for return value, exact value doesn't matter because function is only used in boolean context,
3) use *p++ idiom for even better code.I'm sure there are even better ways to do the comparision using longer words, especially as we know the boundaries and alignment.
This requires terminating dentry names with 1-3 NULs. Al, can we afford such beauty?
Quoted 8 lines · Alexey Dobriyan
Quoted 7 lines · Andi Kleen
Quoted 4 lines · Alexey Dobriyan
1) consistently use "unsigned int" for dentry name length,
2) reuse subtraction result for return value, exact value doesn't matter because function is only used in boolean context,
3) use *p++ idiom for even better code.
Quoted 5 lines
Quoted 2 lines
I'm sure there are even better ways to do the comparision using longer words, especially as we know the boundaries and alignment.
This requires terminating dentry names with 1-3 NULs. Al, can we afford such beauty?
Hmm.
At least, in link_path_walk(), there is no room to insert NULs. --
To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Quoted 6 lines
Quoted 2 lines
This requires terminating dentry names with 1-3 NULs. Al, can we afford such beauty?
Hmm.
At least, in
link_path_walk(), there is no room to insert NULs.
We don't necessarily need to pad. It's enough to use the word compare as a fast path.
Of course memcpy should do it already, but it may be inefficient for small strings.
-Andi
Quoted 1 line
Signature · 1 line
[email protected] -- Speaking for myself only.
Quoted 7 lines · Alexey Dobriyan
1) consistently use "unsigned int" for dentry name length,
2) reuse subtraction result for return value, exact value doesn't matter because function is only used in boolean context,
3) use *p++ idiom for even better code.All of this results in performance speedup of "git diff" which is way out of statistical error (0.4% vs 0.15% of 3 sigma):
On what machine, out of interest?
Signature · 4 lines
Matthew Wilcox Intel Open Source Technology Centre "Bill, look, we understand that you're interested in selling us this operating system, but compare it to ours. We can't possibly take such a retrograde step."
Quoted 10 lines · Matthew Wilcox
Quoted 7 lines · Alexey Dobriyan
1) consistently use "unsigned int" for dentry name length,
2) reuse subtraction result for return value, exact value doesn't matter because function is only used in boolean context,
3) use *p++ idiom for even better code.All of this results in performance speedup of "git diff" which is way out of statistical error (0.4% vs 0.15% of 3 sigma):
On what machine, out of interest?
Core i5 760 (x86_64)
Quoted 7 lines · Alexey Dobriyan
1) consistently use "unsigned int" for dentry name length,
2) reuse subtraction result for return value, exact value doesn't matter because function is only used in boolean context,
3) use *p++ idiom for even better code.All of this results in performance speedup of "git diff" which is way out of statistical error (0.4% vs 0.15% of 3 sigma):
Would you have any interest to port this patch on top of Linus' latest changes there? 0.4% increase is nothing to sneeze at. There may be some improvements with the DCACHE_WORD_ACCESS code too.