user/sven/linux.git/lib/int_sqrt.c, branch v4.7

lib/int_sqrt.c: optimize square root algorithm

2013-04-30T01:28:19Z

Optimize the current version of the shift-and-subtract (hardware) algorithm, described by John von Newmann[1] and Guy L Steele. Iterating 1,000,000 times, perf shows for the current version: Performance counter stats for './sqrt-curr' (10 runs): 27.170996 task-clock # 0.979 CPUs utilized ( +- 3.19% ) 3 context-switches # 0.103 K/sec ( +- 4.76% ) 0 cpu-migrations # 0.004 K/sec ( +-100.00% ) 104 page-faults # 0.004 M/sec ( +- 0.16% ) 64,921,199 cycles # 2.389 GHz ( +- 0.03% ) 28,967,789 stalled-cycles-frontend # 44.62% frontend cycles idle ( +- 0.18% ) stalled-cycles-backend 104,502,623 instructions # 1.61 insns per cycle # 0.28 stalled cycles per insn ( +- 0.00% ) 34,088,368 branches # 1254.587 M/sec ( +- 0.00% ) 4,901 branch-misses # 0.01% of all branches ( +- 1.32% ) 0.027763015 seconds time elapsed ( +- 3.22% ) And for the new version: Performance counter stats for './sqrt-new' (10 runs): 0.496869 task-clock # 0.519 CPUs utilized ( +- 2.38% ) 0 context-switches # 0.000 K/sec 0 cpu-migrations # 0.403 K/sec ( +-100.00% ) 104 page-faults # 0.209 M/sec ( +- 0.15% ) 590,760 cycles # 1.189 GHz ( +- 2.35% ) 395,053 stalled-cycles-frontend # 66.87% frontend cycles idle ( +- 3.67% ) stalled-cycles-backend 398,963 instructions # 0.68 insns per cycle # 0.99 stalled cycles per insn ( +- 0.39% ) 70,228 branches # 141.341 M/sec ( +- 0.36% ) 3,364 branch-misses # 4.79% of all branches ( +- 5.45% ) 0.000957440 seconds time elapsed ( +- 2.42% ) Furthermore, this saves space in instruction text: text data bss dec hex filename 111 0 0 111 6f lib/int_sqrt-baseline.o 89 0 0 89 59 lib/int_sqrt.o [1] http://en.wikipedia.org/wiki/First_Draft_of_a_Report_on_the_EDVAC Signed-off-by: Davidlohr Bueso Reviewed-by: Jonathan Gonzalez Tested-by: Jonathan Gonzalez Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds

lib: reduce the use of module.h wherever possible

2012-03-07T20:04:04Z

For files only using THIS_MODULE and/or EXPORT_SYMBOL, map them onto including export.h -- or if the file isn't even using those, then just delete the include. Fix up any implicit include dependencies that were being masked by module.h along the way. Signed-off-by: Paul Gortmaker

[PATCH] lib: Fix bug in int_sqrt() for 64 bit longs

2006-02-03T16:32:08Z

The implementation of int_sqrt() assumes that longs have 32 bits. On systems that have 64 bit longs this will result in gross errors when the argument to the function is greater than 2^32 - 1 on such systems. I doubt whether any such use is currently made of int_sqrt() but the attached patch fixes the problem anyway. Signed-off-by: Peter Williams Cc: Dave Jones Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds

[PATCH] sqrt() fixes

2003-12-29T13:42:51Z

It turns out that the int_sqrt() function in oom_kill.c gets it wrong. But fb_sqrt() in fbmon.c gets its math right. Move that function into lib/int_sqrt.c, and consolidate. (oom_kill.c fix from Thomas Schlichter )