[Openmcl-devel] just when you thought it was safe to go back in the CCL trunk

[Ron Garret]

Awesome!

This actually turns out to be what I was after:

(defun foo (a i j k)
  (declare (type (simple-array (unsigned-byte 64) (*)) a)
           (type fixnum i j k)
           (optimize (speed 3) (safety 0) (debug 0)))
  (setf (aref a k) (the (unsigned-byte 64)(+ (aref a i) (aref a j))))
  nil)

Returning NIL turns out to be the trick that makes it work.  If you don’t do that, the code ends up being much longer.  (Disassembling both versions is very illuminating.)

Thanks!

rg

On Sep 16, 2015, at 12:34 AM, Gary Byers <gb at clozure.com> wrote:

> I misremembered.
> 
> 
> 
> On 09/14/2015 07:30 PM, Gary Byers wrote:
>> the idiom may be something like
>> (defun foo (a i j k) (declare (type (simple-array (unsigned-byte 64) (*)) a))
>>  (setf (aref a k) (the (unsigned-byte 64)(+ (aref a i) (aref a j)))))
> 
> as written, that will set the a[K] to the sum of a[i] and a[j] and return that sum
> as a  lisp integer.
> If you just want to store the sum in the Kth element of the vector. don't return it. e.g
> 
> 
> (defun foo (a i j k)
>   (declare (type (simple-array (unsigned-byte 64) (*)) a))
>  (setf (aref a k) (the (unsigned-byte 64)(+ (aref a i) (aref a j))))
>   nil)
> 
>> There may be other issues involved here,
>> 
> 
> There are, but think that the code above does what you (Ron) asked for
> If someone wanted all 65 bits of the sum, I'm not sure whther or not
> the code in that similar case tries to detect overflow.
> 
>> 
>> On 09/14/2015 06:16 PM, Ron Garret wrote:
>>> On Sep 14, 2015, at 2:09 PM, Gary Byers <gb at clozure.com> wrote:
>>> 
>>>> Here is the threatened documementation.
>>> Thanks Gary, that’s actually very interesting reading!  (At least it was to me, but I guess that makes me a pretty hard-core geek.)
>>> 
>>> As long as the compiler is on the table, I have a question that I’ve been meaning to ask for a long time but never quite found the right moment.  I’m not sure this is the right moment, but here goes anyway…
>>> 
>>> I’m working on cryptography nowadays, and that involves doing a lot of operations on quantities that are constrained to be 32 or 64 bits wide, and it is important that those operations happen in constant time in order not to leak secrets through timing and other side-channel attacks.
>>> 
>>> Straightforward Lisp code is not suited for this because some N-bit values on an N-bit machine are fixnums and others are bignums.  But there is a way to express the desired semantics cleanly, and that is to declare things as signed-byte and unsigned-byte values.  In particular, vectors whose element types are (un/signed-byte 32) or (un/signed-byte 64) can hold 32-bit and 64-bit values cleanly with no boxing.  In principle, this should allow Lisp code operating on such values and putting the results back in such places to be as fast as C code.
>>> 
>>> But there is a fly in the ointment: Common Lisp does not include modulo 2^N arithmetic as primitives.  You can only do mod 2^N math as an idiom, i.e. (setf (some-place-that-has-been-declared-to-be (type (un/signed-byte 32)) (mod (op v1 v2) #.(ash 1 32))).  It is asking an awful lot of the compiler to recognize such idioms as optimizable into one or two machine instructions.  And yet, it would be so tremendously useful, not just for crypto, but for image processing as well.
>>> 
>>> How hard would be to tweak the compiler so that it could make this optimization?  Specifically, how feasible would it be for the compiler to recognize the above as a special case and optimize it to (more or less) what a C compiler would produce? AFAICT it shouldn’t be too difficult, and if it were done, I think it would let CCL kick some serious benchmarking tushie.
>>> 
>>> Is such a thing feasible?
>>> 
>>> rg
>>> 
>> 
>> _______________________________________________
>> Openmcl-devel mailing list
>> Openmcl-devel at clozure.com
>> https://lists.clozure.com/mailman/listinfo/openmcl-devel
> 
> _______________________________________________
> Openmcl-devel mailing list
> Openmcl-devel at clozure.com
> https://lists.clozure.com/mailman/listinfo/openmcl-devel