[Caml-list] [ANN] bigstring 0.1

[Caml-list] [ANN] bigstring 0.1

[Simon Cruanes]

[-- Attachment #1: Type: text/plain, Size: 505 bytes --]

Hello,

I released bigstring.0.1 yesterday, a small module for dealing with
bigarrays of chars. It used to be part of containers, but is useful on
its own for low level IO, mirage, etc.; hence the split.  The license is
BSD-2-clauses.

Code, issues, etc. can be found at https://github.com/c-cube/ocaml-bigstring ,
and contributions and criticism are welcome.

Cheers,

-- 
Simon Cruanes

http://weusepgp.info/
key 49AA62B6, fingerprint 949F EB87 8F06 59C6 D7D3  7D8D 4AC0 1D08 49AA 62B6

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

[Caml-list] Constant-time function

[Chan Ngo]

Dear all,

I have write a simple function to compare two lists as below:

let rec lcomp l1 l2 = 
  if (List.length l1 != List.length l2) 
  then false
  else match l1, l2 with 
  | h1::t1, h2::t2 -> h1 = h2 && lcomp t1 t2
  | _, _ -> true;;

In theory, we can see that the execution is a function of length of l1 and l2 (in case they are same length, otherwise it return immediately) and it is constant time (i.e., we fixed the length of l1 and l2). However, in fact, when I run this function with two lists of around 100 elements, 
+ with only 10th element is different: it takes 0.000027s
+ with only 90th element is different: it takes 0.000116s

You see the execution times are really different. Thus, I wonder that the compiler did some optimization? Does anyone have some pointers?

Thanks,
Chan


> On Feb 22, 2016, at 4:48 AM, Simon Cruanes <simon.cruanes.2007@m4x.org> wrote:
> 
> Hello,
> 
> I released bigstring.0.1 yesterday, a small module for dealing with
> bigarrays of chars. It used to be part of containers, but is useful on
> its own for low level IO, mirage, etc.; hence the split.  The license is
> BSD-2-clauses.
> 
> Code, issues, etc. can be found at https://github.com/c-cube/ocaml-bigstring ,
> and contributions and criticism are welcome.
> 
> Cheers,
> 
> -- 
> Simon Cruanes
> 
> http://weusepgp.info/
> key 49AA62B6, fingerprint 949F EB87 8F06 59C6 D7D3  7D8D 4AC0 1D08 49AA 62B6

Re: [Caml-list] Constant-time function

[Anton Bachin]

1. You are computing the length of l1 and l2 every iteration. On the first iteration, it is the lengths of the original lists. On the second iteration, it is the lengths of their tails. This function takes time quadratic in the maximum of (length l1, length l2), as written. List.length itself takes linear time.

2. If h1 and h2 are nontrivial types, structural equality may take a nontrivial amount of time to compute.

> On Feb 22, 2016, at 13:45, Chan Ngo <chan.ngo2203@gmail.com> wrote:
> 
> Dear all,
> 
> I have write a simple function to compare two lists as below:
> 
> let rec lcomp l1 l2 = 
>  if (List.length l1 != List.length l2) 
>  then false
>  else match l1, l2 with 
>  | h1::t1, h2::t2 -> h1 = h2 && lcomp t1 t2
>  | _, _ -> true;;
> 
> In theory, we can see that the execution is a function of length of l1 and l2 (in case they are same length, otherwise it return immediately) and it is constant time (i.e., we fixed the length of l1 and l2). However, in fact, when I run this function with two lists of around 100 elements, 
> + with only 10th element is different: it takes 0.000027s
> + with only 90th element is different: it takes 0.000116s
> 
> You see the execution times are really different. Thus, I wonder that the compiler did some optimization? Does anyone have some pointers?
> 
> Thanks,
> Chan
> 
> 
>> On Feb 22, 2016, at 4:48 AM, Simon Cruanes <simon.cruanes.2007@m4x.org> wrote:
>> 
>> Hello,
>> 
>> I released bigstring.0.1 yesterday, a small module for dealing with
>> bigarrays of chars. It used to be part of containers, but is useful on
>> its own for low level IO, mirage, etc.; hence the split.  The license is
>> BSD-2-clauses.
>> 
>> Code, issues, etc. can be found at https://github.com/c-cube/ocaml-bigstring ,
>> and contributions and criticism are welcome.
>> 
>> Cheers,
>> 
>> -- 
>> Simon Cruanes
>> 
>> http://weusepgp.info/
>> key 49AA62B6, fingerprint 949F EB87 8F06 59C6 D7D3  7D8D 4AC0 1D08 49AA 62B6
> 
> 
> -- 
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

Re: [Caml-list] Constant-time function

[Anton Bachin]

Correction: "if h1 and h2 are of nontrivial type”.

> On Feb 22, 2016, at 13:51, Anton Bachin <antronbachin@gmail.com> wrote:
> 
> 1. You are computing the length of l1 and l2 every iteration. On the first iteration, it is the lengths of the original lists. On the second iteration, it is the lengths of their tails. This function takes time quadratic in the maximum of (length l1, length l2), as written. List.length itself takes linear time.
> 
> 2. If h1 and h2 are nontrivial types, structural equality may take a nontrivial amount of time to compute.
> 
>> On Feb 22, 2016, at 13:45, Chan Ngo <chan.ngo2203@gmail.com> wrote:
>> 
>> Dear all,
>> 
>> I have write a simple function to compare two lists as below:
>> 
>> let rec lcomp l1 l2 = 
>> if (List.length l1 != List.length l2) 
>> then false
>> else match l1, l2 with 
>> | h1::t1, h2::t2 -> h1 = h2 && lcomp t1 t2
>> | _, _ -> true;;
>> 
>> In theory, we can see that the execution is a function of length of l1 and l2 (in case they are same length, otherwise it return immediately) and it is constant time (i.e., we fixed the length of l1 and l2). However, in fact, when I run this function with two lists of around 100 elements, 
>> + with only 10th element is different: it takes 0.000027s
>> + with only 90th element is different: it takes 0.000116s
>> 
>> You see the execution times are really different. Thus, I wonder that the compiler did some optimization? Does anyone have some pointers?
>> 
>> Thanks,
>> Chan
>> 
>> 
>>> On Feb 22, 2016, at 4:48 AM, Simon Cruanes <simon.cruanes.2007@m4x.org> wrote:
>>> 
>>> Hello,
>>> 
>>> I released bigstring.0.1 yesterday, a small module for dealing with
>>> bigarrays of chars. It used to be part of containers, but is useful on
>>> its own for low level IO, mirage, etc.; hence the split.  The license is
>>> BSD-2-clauses.
>>> 
>>> Code, issues, etc. can be found at https://github.com/c-cube/ocaml-bigstring ,
>>> and contributions and criticism are welcome.
>>> 
>>> Cheers,
>>> 
>>> -- 
>>> Simon Cruanes
>>> 
>>> http://weusepgp.info/
>>> key 49AA62B6, fingerprint 949F EB87 8F06 59C6 D7D3  7D8D 4AC0 1D08 49AA 62B6
>> 
>> 
>> -- 
>> Caml-list mailing list.  Subscription management and archives:
>> https://sympa.inria.fr/sympa/arc/caml-list
>> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>> Bug reports: http://caml.inria.fr/bin/caml-bugs
> 
> 
> -- 
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

Re: [Caml-list] Constant-time function

[Chan Ngo]

Hi Johannes and Anton,

thanks for the information, but I did not mean the time complexity of the function is constant (Big O notation). I mean the amount of time of execution is constant when we fix the list length.

In fact, I want to write a function that the running time is constant (not the time complexity) given the size of input is fixed. That means it does not depend on the characteristic of the input.

Best,
Chan

> On Feb 22, 2016, at 2:51 PM, Anton Bachin <antronbachin@gmail.com> wrote:
> 
> 1. You are computing the length of l1 and l2 every iteration. On the first iteration, it is the lengths of the original lists. On the second iteration, it is the lengths of their tails. This function takes time quadratic in the maximum of (length l1, length l2), as written. List.length itself takes linear time.
> 
> 2. If h1 and h2 are nontrivial types, structural equality may take a nontrivial amount of time to compute.
> 
>> On Feb 22, 2016, at 13:45, Chan Ngo <chan.ngo2203@gmail.com> wrote:
>> 
>> Dear all,
>> 
>> I have write a simple function to compare two lists as below:
>> 
>> let rec lcomp l1 l2 = 
>> if (List.length l1 != List.length l2) 
>> then false
>> else match l1, l2 with 
>> | h1::t1, h2::t2 -> h1 = h2 && lcomp t1 t2
>> | _, _ -> true;;
>> 
>> In theory, we can see that the execution is a function of length of l1 and l2 (in case they are same length, otherwise it return immediately) and it is constant time (i.e., we fixed the length of l1 and l2). However, in fact, when I run this function with two lists of around 100 elements, 
>> + with only 10th element is different: it takes 0.000027s
>> + with only 90th element is different: it takes 0.000116s
>> 
>> You see the execution times are really different. Thus, I wonder that the compiler did some optimization? Does anyone have some pointers?
>> 
>> Thanks,
>> Chan
>> 
>> 
>>> On Feb 22, 2016, at 4:48 AM, Simon Cruanes <simon.cruanes.2007@m4x.org> wrote:
>>> 
>>> Hello,
>>> 
>>> I released bigstring.0.1 yesterday, a small module for dealing with
>>> bigarrays of chars. It used to be part of containers, but is useful on
>>> its own for low level IO, mirage, etc.; hence the split.  The license is
>>> BSD-2-clauses.
>>> 
>>> Code, issues, etc. can be found at https://github.com/c-cube/ocaml-bigstring ,
>>> and contributions and criticism are welcome.
>>> 
>>> Cheers,
>>> 
>>> -- 
>>> Simon Cruanes
>>> 
>>> http://weusepgp.info/
>>> key 49AA62B6, fingerprint 949F EB87 8F06 59C6 D7D3  7D8D 4AC0 1D08 49AA 62B6
>> 
>> 
>> -- 
>> Caml-list mailing list.  Subscription management and archives:
>> https://sympa.inria.fr/sympa/arc/caml-list
>> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>> Bug reports: http://caml.inria.fr/bin/caml-bugs
> 

Re: [Caml-list] Constant-time function

[Anton Bachin]

But the complexity of this function is not constant if you fix only the list length. It still varies quadratically in the location of the first pair of elements that are different, because the “outer iteration” is performed that many times, and the “inner" List.lengths visit at least that many elements each time, since this location (if it exists) is less than the list length. Hence, the behavior you are observing.

> On Feb 22, 2016, at 13:57, Chan Ngo <chan.ngo2203@gmail.com> wrote:
> 
> Hi Johannes and Anton,
> 
> thanks for the information, but I did not mean the time complexity of the function is constant (Big O notation). I mean the amount of time of execution is constant when we fix the list length.
> 
> In fact, I want to write a function that the running time is constant (not the time complexity) given the size of input is fixed. That means it does not depend on the characteristic of the input.
> 
> Best,
> Chan
> 
>> On Feb 22, 2016, at 2:51 PM, Anton Bachin <antronbachin@gmail.com> wrote:
>> 
>> 1. You are computing the length of l1 and l2 every iteration. On the first iteration, it is the lengths of the original lists. On the second iteration, it is the lengths of their tails. This function takes time quadratic in the maximum of (length l1, length l2), as written. List.length itself takes linear time.
>> 
>> 2. If h1 and h2 are nontrivial types, structural equality may take a nontrivial amount of time to compute.
>> 
>>> On Feb 22, 2016, at 13:45, Chan Ngo <chan.ngo2203@gmail.com> wrote:
>>> 
>>> Dear all,
>>> 
>>> I have write a simple function to compare two lists as below:
>>> 
>>> let rec lcomp l1 l2 = 
>>> if (List.length l1 != List.length l2) 
>>> then false
>>> else match l1, l2 with 
>>> | h1::t1, h2::t2 -> h1 = h2 && lcomp t1 t2
>>> | _, _ -> true;;
>>> 
>>> In theory, we can see that the execution is a function of length of l1 and l2 (in case they are same length, otherwise it return immediately) and it is constant time (i.e., we fixed the length of l1 and l2). However, in fact, when I run this function with two lists of around 100 elements, 
>>> + with only 10th element is different: it takes 0.000027s
>>> + with only 90th element is different: it takes 0.000116s
>>> 
>>> You see the execution times are really different. Thus, I wonder that the compiler did some optimization? Does anyone have some pointers?
>>> 
>>> Thanks,
>>> Chan
>>> 
>>> 
>>>> On Feb 22, 2016, at 4:48 AM, Simon Cruanes <simon.cruanes.2007@m4x.org> wrote:
>>>> 
>>>> Hello,
>>>> 
>>>> I released bigstring.0.1 yesterday, a small module for dealing with
>>>> bigarrays of chars. It used to be part of containers, but is useful on
>>>> its own for low level IO, mirage, etc.; hence the split.  The license is
>>>> BSD-2-clauses.
>>>> 
>>>> Code, issues, etc. can be found at https://github.com/c-cube/ocaml-bigstring ,
>>>> and contributions and criticism are welcome.
>>>> 
>>>> Cheers,
>>>> 
>>>> -- 
>>>> Simon Cruanes
>>>> 
>>>> http://weusepgp.info/
>>>> key 49AA62B6, fingerprint 949F EB87 8F06 59C6 D7D3  7D8D 4AC0 1D08 49AA 62B6
>>> 
>>> 
>>> -- 
>>> Caml-list mailing list.  Subscription management and archives:
>>> https://sympa.inria.fr/sympa/arc/caml-list
>>> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>>> Bug reports: http://caml.inria.fr/bin/caml-bugs
>> 
> 

Re: [Caml-list] Constant-time function

[Milan Stanojević]

[-- Attachment #1: Type: text/plain, Size: 4260 bytes --]

Chan, I think you're confused because you expect that the function will
visit each element of the lists (if they are the same size).
Compiler short circuits && operator so your loop runs only til the first
element that differs. If you swap the arguments to && you should get the
behavior of visiting all elements (which is of course undesirable in
practice)
On Feb 22, 2016 15:02, "Anton Bachin" <antronbachin@gmail.com> wrote:

> But the complexity of this function is not constant if you fix only the
> list length. It still varies quadratically in the location of the first
> pair of elements that are different, because the “outer iteration” is
> performed that many times, and the “inner" List.lengths visit at least that
> many elements each time, since this location (if it exists) is less than
> the list length. Hence, the behavior you are observing.
>
> > On Feb 22, 2016, at 13:57, Chan Ngo <chan.ngo2203@gmail.com> wrote:
> >
> > Hi Johannes and Anton,
> >
> > thanks for the information, but I did not mean the time complexity of
> the function is constant (Big O notation). I mean the amount of time of
> execution is constant when we fix the list length.
> >
> > In fact, I want to write a function that the running time is constant
> (not the time complexity) given the size of input is fixed. That means it
> does not depend on the characteristic of the input.
> >
> > Best,
> > Chan
> >
> >> On Feb 22, 2016, at 2:51 PM, Anton Bachin <antronbachin@gmail.com>
> wrote:
> >>
> >> 1. You are computing the length of l1 and l2 every iteration. On the
> first iteration, it is the lengths of the original lists. On the second
> iteration, it is the lengths of their tails. This function takes time
> quadratic in the maximum of (length l1, length l2), as written. List.length
> itself takes linear time.
> >>
> >> 2. If h1 and h2 are nontrivial types, structural equality may take a
> nontrivial amount of time to compute.
> >>
> >>> On Feb 22, 2016, at 13:45, Chan Ngo <chan.ngo2203@gmail.com> wrote:
> >>>
> >>> Dear all,
> >>>
> >>> I have write a simple function to compare two lists as below:
> >>>
> >>> let rec lcomp l1 l2 =
> >>> if (List.length l1 != List.length l2)
> >>> then false
> >>> else match l1, l2 with
> >>> | h1::t1, h2::t2 -> h1 = h2 && lcomp t1 t2
> >>> | _, _ -> true;;
> >>>
> >>> In theory, we can see that the execution is a function of length of l1
> and l2 (in case they are same length, otherwise it return immediately) and
> it is constant time (i.e., we fixed the length of l1 and l2). However, in
> fact, when I run this function with two lists of around 100 elements,
> >>> + with only 10th element is different: it takes 0.000027s
> >>> + with only 90th element is different: it takes 0.000116s
> >>>
> >>> You see the execution times are really different. Thus, I wonder that
> the compiler did some optimization? Does anyone have some pointers?
> >>>
> >>> Thanks,
> >>> Chan
> >>>
> >>>
> >>>> On Feb 22, 2016, at 4:48 AM, Simon Cruanes <
> simon.cruanes.2007@m4x.org> wrote:
> >>>>
> >>>> Hello,
> >>>>
> >>>> I released bigstring.0.1 yesterday, a small module for dealing with
> >>>> bigarrays of chars. It used to be part of containers, but is useful on
> >>>> its own for low level IO, mirage, etc.; hence the split.  The license
> is
> >>>> BSD-2-clauses.
> >>>>
> >>>> Code, issues, etc. can be found at
> https://github.com/c-cube/ocaml-bigstring ,
> >>>> and contributions and criticism are welcome.
> >>>>
> >>>> Cheers,
> >>>>
> >>>> --
> >>>> Simon Cruanes
> >>>>
> >>>> http://weusepgp.info/
> >>>> key 49AA62B6, fingerprint 949F EB87 8F06 59C6 D7D3  7D8D 4AC0 1D08
> 49AA 62B6
> >>>
> >>>
> >>> --
> >>> Caml-list mailing list.  Subscription management and archives:
> >>> https://sympa.inria.fr/sympa/arc/caml-list
> >>> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> >>> Bug reports: http://caml.inria.fr/bin/caml-bugs
> >>
> >
>
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

[-- Attachment #2: Type: text/html, Size: 6105 bytes --]

Re: [Caml-list] Constant-time function

[Chan Ngo]

[-- Attachment #1: Type: text/plain, Size: 675 bytes --]

Hi Milan,

thanks, I see what you mentioned with the “&&” operator. In fact, one case the behavior as I wanted is in crypto primitive (we need constant-time function to avoid time side-channel attack, for example, give any input for comparing with the secret hash value with fixed size, the time execution of comparing is constant.

Best,
Chan

> On Feb 22, 2016, at 3:12 PM, Milan Stanojević <milanst@gmail.com> wrote:
> 
> Compiler short circuits && operator so your loop runs only til the first element that differs. If you swap the arguments to && you should get the behavior of visiting all elements (which is of course undesirable in practice)
> 
> 


[-- Attachment #2: Type: text/html, Size: 1594 bytes --]

Re: [Caml-list] Constant-time function

[Milan Stanojević]

[-- Attachment #1: Type: text/plain, Size: 1220 bytes --]

Oh, that's tricky then.
I mean, it's not hard to make this particular function behave how you want,
but in general ocaml compiler might optimize some constructs such that time
behavior of your code changes slightly (and in some cases a lot). For
example allocation can increase or decrease with small changes which will
affect your program's running time.
Now, I don't know much about crypto so I don't know how much you care about
this.
On Feb 22, 2016 15:16, "Chan Ngo" <chan.ngo2203@gmail.com> wrote:

> Hi Milan,
>
> thanks, I see what you mentioned with the “&&” operator. In fact, one case
> the behavior as I wanted is in crypto primitive (we need constant-time
> function to avoid time side-channel attack, for example, give any input for
> comparing with the secret hash value with fixed size, the time execution of
> comparing is constant.
>
> Best,
> Chan
>
> On Feb 22, 2016, at 3:12 PM, Milan Stanojević <milanst@gmail.com> wrote:
>
> Compiler short circuits && operator so your loop runs only til the first
> element that differs. If you swap the arguments to && you should get the
> behavior of visiting all elements (which is of course undesirable in
> practice)
>
>
>

[-- Attachment #2: Type: text/html, Size: 1937 bytes --]

Re: [Caml-list] Constant-time function

[Gerd Stolpmann]

[-- Attachment #1: Type: text/plain, Size: 1371 bytes --]

Am Montag, den 22.02.2016, 15:16 -0500 schrieb Chan Ngo:
> Hi Milan,
> 
> 
> thanks, I see what you mentioned with the “&&” operator. In fact, one
> case the behavior as I wanted is in crypto primitive (we need
> constant-time function to avoid time side-channel attack, for example,
> give any input for comparing with the secret hash value with fixed
> size, the time execution of comparing is constant.

You can define an operator that behaves like this:

let ( &&& ) p q = p && q

There might be other functions whose run time varies with the input.
E.g. (string) equality comes to my mind.

Gerd

> 
> Best,
> Chan
> 
> > On Feb 22, 2016, at 3:12 PM, Milan Stanojević <milanst@gmail.com>
> > wrote:
> > 
> > Compiler short circuits && operator so your loop runs only til the
> > first element that differs. If you swap the arguments to && you
> > should get the behavior of visiting all elements (which is of course
> > undesirable in practice)
> > 
> > 
> > 
> 
> 

-- 
------------------------------------------------------------
Gerd Stolpmann, Darmstadt, Germany    gerd@gerd-stolpmann.de
My OCaml site:          http://www.camlcity.org
Contact details:        http://www.camlcity.org/contact.html
Company homepage:       http://www.gerd-stolpmann.de
------------------------------------------------------------


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 473 bytes --]