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

tcl super dude tcleval at gmail.com
Sun Nov 4 19:22:17 EST 2012


As on https://github.com/feeley/gambit/blob/master/include/gambit.h.in line
2615
I guess 'min' procedure is just a C macro ....


...
/* APPLY-able operations */

#define ___FIX_0 ___FIX(0)
#define ___FIXPOS(x)((___WORD)(x))
#define ___FIXMAX(x,y)(((x)<(y))?(y):(x))
#define ___FIXMIN(x,y)(((x)<(y))?(x):(y))  <----------- the line in question
#define ___FIXADD(x,y)((___WORD)((x)+(y)))

...

this way there is no call frame. Maybe later Marc can put some light
to the matter.

obs: I didn't know if I could call you Marc or Mr. Feely, but given
the informal nature  of the mailing-list I prefer call people by their
first name/nick, I hope you don't mind.


On Sun, Nov 4, 2012 at 9:12 PM, tcl super dude <tcleval at gmail.com> wrote:

> 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/8007129b/attachment.htm>


More information about the Gambit-list mailing list