[gambit-list] Slow Bit Hacking with c-lambda

tcl super dude tcleval at gmail.com
Sun Nov 4 19:12:44 EST 2012


here I have the expansion, assembly, C, and scheme

On Sun, Nov 4, 2012 at 8:01 PM, Mikael <mikael.rcv at gmail.com> wrote:

> 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/20121104/371d6720/attachment.htm>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: bithacks2.s
Type: application/octet-stream
Size: 26569 bytes
Desc: not available
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20121104/371d6720/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: bithacks2.scm
Type: application/octet-stream
Size: 1377 bytes
Desc: not available
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20121104/371d6720/attachment-0001.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: bithacks2.c
Type: text/x-csrc
Size: 22834 bytes
Desc: not available
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20121104/371d6720/attachment.c>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: expansion.scm
Type: application/octet-stream
Size: 6985 bytes
Desc: not available
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20121104/371d6720/attachment-0002.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: bithacks2_.c
Type: text/x-csrc
Size: 449937 bytes
Desc: not available
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20121104/371d6720/attachment-0001.c>


More information about the Gambit-list mailing list