[gambit-list] Slow Bit Hacking with c-lambda
Mikael
mikael.rcv at gmail.com
Sun Nov 4 18:01:08 EST 2012
What about you catch a copy of the C code post- macro expansion, and a copy
of the assembly output too, and have a look?
Let the ml know what you found.
2012/11/5 tcl super dude <tcleval at gmail.com>
> 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
>>>
>>>
>>
>
> _______________________________________________
> 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/20121105/9bf911ff/attachment.htm>
More information about the Gambit-list
mailing list