[gambit-list] Slow Bit Hacking with c-lambda
tcl super dude
tcleval at gmail.com
Sun Nov 4 17:50:46 EST 2012
Now scheme min is even faster.. that is ok. But what I don't understand is
how that simple C implementation get so low performance.
abs:
(time (let loop-i ((i 0)) (cond ((fx< i 100000) (set! result (abs i))
(loop-i (fx+ 1 i))))))
1 ms real time
0 ms cpu time (0 user, 0 system)
no collections
no bytes allocated
no minor faults
no major faults
abs-integer:
(time (let loop-j ((j 0)) (cond ((fx< j 100000) (set! result (abs-integer
j)) (loop-j (fx+ 1 j))))))
18 ms real time
17 ms cpu time (17 user, 0 system)
no collections
no bytes allocated
1 minor fault
no major faults
min:
(time (let loop-i ((i 0)) (cond ((fx< i 100000) (set! result (min i
result)) (loop-i (fx+ 1 i))))))
0 ms real time
0 ms cpu time (0 user, 0 system)
no collections
no bytes allocated
no minor faults
no major faults
min-integer:
(time (let loop-j ((j 0)) (cond ((fx< j 100000) (set! result (min-integer j
result)) (loop-j (fx+ 1 j))))))
26 ms real time
26 ms cpu time (23 user, 3 system)
no collections
no bytes allocated
no minor faults
no major faults
On Sun, Nov 4, 2012 at 7:31 PM, Mikael More <mikael.more at gmail.com> wrote:
> Ah, also throw in the following:
> * (declare (not interrupts-enabled))
>
> This might be a big deal - when it's off, Gambit doesn't produce any
> hooks for stack overflow or thread system interrupts but executes your code
> according to a typical C model
>
> * (declare (standard-bindings) (extended-bindings)) too?
>
>
> What is the performance you get from Gambit now, and what kind of
> performance is it you want to get?
>
>
> 2012/11/4 tcl super dude <tcleval at gmail.com>
>
>> I assumed I could get a bit of performance improvement over min procedure
>> because I don't do any branch. I' thought min-integer to be at least close
>> to gambit-c time. The problem is that those operations and a few more are
>> performed thousands of times. Gambit loops are usually 2x slower than C, so
>> I hoped I could improve some basic operations as I only perform them on
>> integers. I don't Understand how a simple shift to extract the lower bits
>> could make so much difference. Maybe if someone point me to the
>> implementation of min and abs on gambit, I can understand the difference. I
>> ve looked for these procedures on gambit's source but could not point it
>> out.
>>
>> I'll try to implement them using vectors and see what happens.
>>
>> now compiled with (block):
>>
>>
>> abs:
>>
>> (time (let loop-i ((i 0)) (cond ((fx< i 100000) (set! result (abs i))
>> (loop-i (fx+ 1 i))))))
>> 2 ms real time
>>
>> 3 ms cpu time (3 user, 0 system)
>>
>> no collections
>>
>> no bytes allocated
>>
>> no minor faults
>>
>> no major faults
>>
>> abs-integer:
>>
>> (time (let loop-j ((j 0)) (cond ((fx< j 100000) (set! result (abs-integer
>> j)) (loop-j (fx+ 1 j))))))
>> 19 ms real time
>>
>> 20 ms cpu time (17 user, 3 system)
>>
>> no collections
>>
>> no bytes allocated
>>
>> 2 minor faults
>>
>> no major faults
>>
>> min:
>>
>> (time (let loop-i ((i 0)) (cond ((fx< i 100000) (set! result (min i
>> result)) (loop-i (fx+ 1 i))))))
>> 2 ms real time
>>
>> 3 ms cpu time (0 user, 3 system)
>>
>> no collections
>>
>> no bytes allocated
>>
>> no minor faults
>> no major faults
>> min-integer:
>> (time (let loop-j ((j 0)) (cond ((fx< j 100000) (set! result (min-integer
>> j result)) (loop-j (fx+ 1 j))))))
>> 27 ms real time
>> 27 ms cpu time (27 user, 0 system)
>> no collections
>> no bytes allocated
>> no minor faults
>> no major faults
>>
>>
>> On Sun, Nov 4, 2012 at 5:15 PM, Mikael <mikael.rcv at gmail.com> wrote:
>>
>>> First, please add (declare (block)) and re-compile, this way Gambit
>>> won't need to re-look up the procedures in the global namespace that you
>>> call, on each invocation. Please report what kind of improvement you got
>>> with this.
>>>
>>>
>>> Now just to make this round of emails complete:
>>>
>>> What would be good/very good performance in your view?
>>>
>>> Could you send jobs in some kind of batch format to C?
>>>
>>> Note that Gambit-internal fxnum variables have a special encoding (the
>>> lowermost two(?) bits are object type identifier, which are shifted out
>>> when converting them to C int), this takes a little bit of time.
>>>
>>> If for instance you make u32vectors/s32vectors/etc. [and send batch ops
>>> made on those to C to be performed etc.] then you can just read out the
>>> content of those vectors 'raw' in C, there's no interconversion there.
>>>
>>> Brgds
>>>
>>> 2012/11/4 tcl super dude <tcleval at gmail.com>
>>>
>>>> Hi everyone,
>>>>
>>>> I have been working on an image processing library that I want to use
>>>> on android. I know that performance is a bit of a problem on image
>>>> processing, so I started to study some bit hacking to improve the
>>>> performance on my integer operations. My problem now is that I don't know
>>>> why my c-lambdas take so much time to execute. All operations take constant
>>>> time and there is no branching. Probably is some sort of conversion time
>>>> between C types and GAMBIT types. I expected min-integer and abs-integer to
>>>> be a lot faster than min and abs, respectively. Any help is appreciated.
>>>>
>>>> URL REFERENCE:
>>>> http://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs
>>>> http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax
>>>>
>>>>
>>>> MY ENVIRONMENT:
>>>> Linux casa 3.6.4-1-ARCH #1 SMP PREEMPT Mon Oct 29 15:13:56 CET 2012
>>>> i686 GNU/Linux
>>>>
>>>> gcc -v
>>>> Using built-in specs.
>>>> COLLECT_GCC=gcc
>>>> COLLECT_LTO_WRAPPER=/usr/lib/gcc/i686-pc-linux-gnu/4.7.2/lto-wrapper
>>>> Target: i686-pc-linux-gnu
>>>> Configured with: /build/src/gcc-4.7.2/configure --prefix=/usr
>>>> --libdir=/usr/lib --libexecdir=/usr/lib --mandir=/usr/share/man
>>>> --infodir=/usr/share/info --with-bugurl=https://bugs.archlinux.org/--enable-languages=c,c++,ada,fortran,go,lto,objc,obj-c++ --enable-shared
>>>> --enable-threads=posix --with-system-zlib --enable-__cxa_atexit
>>>> --disable-libunwind-exceptions --enable-clocale=gnu --disable-libstdcxx-pch
>>>> --enable-libstdcxx-time --enable-gnu-unique-object --enable-linker-build-id
>>>> --with-ppl --enable-cloog-backend=isl --disable-ppl-version-check
>>>> --disable-cloog-version-check --enable-lto --enable-gold
>>>> --enable-ld=default --enable-plugin --with-plugin-ld=ld.gold
>>>> --with-linker-hash-style=gnu --disable-multilib --disable-libssp
>>>> --disable-build-with-cxx --disable-build-poststage1-with-cxx
>>>> --enable-checking=release
>>>> Thread model: posix
>>>> gcc version 4.7.2 (GCC)
>>>>
>>>> Gambit v4.6.6 (SINGLE HOST and GCC extensions enabled)
>>>>
>>>>
>>>> SCHEME CODE: compiled with ---> gambitc -exe bithacks.scm
>>>>
>>>> ;; bithacks.scm
>>>>
>>>>
>>>> (declare
>>>> (not safe)
>>>> (fixnum)
>>>> (inline)
>>>> (inline-primitives))
>>>>
>>>> ;; INTEGER ABSOLUTE
>>>> (define abs-integer
>>>> (c-lambda (int) int
>>>> "// we want to find the absolute value of arg1
>>>> int const mask = ___arg1 >> sizeof(int) * CHAR_BIT - 1;
>>>> ___result = (___arg1 + mask) ^ mask;"))
>>>>
>>>>
>>>> (define min-integer
>>>> (c-lambda (int int) int
>>>> "// find the smaller of arg1 arg2
>>>> ___result = ___arg2 ^ ((___arg1 ^ ___arg2) & -(___arg1 <
>>>> ___arg2));"))
>>>>
>>>> (define (test-abs)
>>>> (let ((result 0))
>>>> (begin
>>>> (display "abs:\n")
>>>> (time
>>>> (let loop-i ((i 0))
>>>> (cond ((fx< i 100000)
>>>> (set! result (abs i))
>>>> (loop-i (fx+ 1 i))))))
>>>> (display "abs-integer:\n")
>>>> (time
>>>> (let loop-j ((j 0))
>>>> (cond ((fx< j 100000)
>>>> (set! result (abs-integer j))
>>>> (loop-j (fx+ 1 j)))))))))
>>>>
>>>> (define (test-min)
>>>> (let ((result 0))
>>>> (begin
>>>> (display "min:\n")
>>>> (time
>>>> (let loop-i ((i 0))
>>>> (cond ((fx< i 100000)
>>>> (set! result (min i result))
>>>> (loop-i (fx+ 1 i))))))
>>>> (display "min-integer:\n")
>>>> (time
>>>> (let loop-j ((j 0))
>>>> (cond ((fx< j 100000)
>>>> (set! result (min-integer j result))
>>>> (loop-j (fx+ 1 j)))))))))
>>>>
>>>> ;; run tests
>>>>
>>>> (test-abs)
>>>> (test-min)
>>>>
>>>> ;;;;;;;;;;;;;;;;;;;;;; RESULTS;;;;;;;;;;;;;;;;;;;;;
>>>>
>>>> abs:
>>>> (time (let loop-i ((i 0)) (cond ((fx< i 100000) (set! result (abs i))
>>>> (loop-i (fx+ 1 i))))))
>>>> 2 ms real time
>>>> 3 ms cpu time (3 user, 0 system)
>>>> no collections
>>>> no bytes allocated
>>>> no minor faults
>>>> no major faults
>>>> abs-integer:
>>>> (time (let loop-j ((j 0)) (cond ((fx< j 100000) (set! result
>>>> (abs-integer j)) (loop-j (fx+ 1 j))))))
>>>> 22 ms real time
>>>> 23 ms cpu time (23 user, 0 system)
>>>> no collections
>>>> no bytes allocated
>>>> 2 minor faults
>>>> no major faults
>>>> min:
>>>> (time (let loop-i ((i 0)) (cond ((fx< i 100000) (set! result (min i
>>>> result)) (loop-i (fx+ 1 i))))))
>>>> 2 ms real time
>>>> 3 ms cpu time (0 user, 3 system)
>>>> no collections
>>>> no bytes allocated
>>>> no minor faults
>>>> no major faults
>>>> min-integer:
>>>> (time (let loop-j ((j 0)) (cond ((fx< j 100000) (set! result
>>>> (min-integer j result)) (loop-j (fx+ 1 j))))))
>>>> 28 ms real time
>>>> 30 ms cpu time (27 user, 3 system)
>>>> no collections
>>>> no bytes allocated
>>>> no minor faults
>>>> no major faults
>>>>
>>>>
>>>> _______________________________________________
>>>> Gambit-list mailing list
>>>> Gambit-list at iro.umontreal.ca
>>>> https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
>>>>
>>>>
>>>
>>
>> _______________________________________________
>> Gambit-list mailing list
>> Gambit-list at iro.umontreal.ca
>> https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20121104/0f9d77c6/attachment.htm>
More information about the Gambit-list
mailing list