[Caml-list] How could I implement an efficient ring buffer?

[Caml-list] How could I implement an efficient ring buffer?

[Hongbo Zhang]

Hi List,
    I want to implement sliding window algorithm (in place, no memory 
copy), I wonder whether I need to write c code.

    To make it clear and simple,
       In c, you can record the head pointer of the array, and do the 
modulo operations when get and set
       In ocaml, it seems you have an array a of type int array,  you 
can not do things like this *(&a+5).
    Many thanks

RE: [Caml-list] How could I implement an efficient ring buffer?

[David Allsopp]

Hongbo Zhang wrote:
> Hi List,
>     I want to implement sliding window algorithm (in place, no memory
> copy), I wonder whether I need to write c code.
> 
>     To make it clear and simple,
>        In c, you can record the head pointer of the array, and do the
> modulo operations when get and set
>        In ocaml, it seems you have an array a of type int array,  you can
> not do things like this *(&a+5).

Perhaps I'm missing something, but if you're planning on using arrays, what's wrong with retrieving the item using the array index modulo the length of the array?

i.e.

let a = [| ... or whatever ... |] in
a.(5 mod Array.length a)

If accessing an array by index instead of by pointer worries you, then you're looking at the wrong language ;o)


David

Re: [Caml-list] How could I implement an efficient ring buffer?

[Gabriel Scherer]

A small implementation of a FIFO queue implemented as a circular
buffer of fixed length:

type 'a circular_buffer = {
  mutable pos : int;
  mutable count : int;
  data : 'a array;
  size : int;
}

let create size dummy = {
  pos = 0;
  count = 0;
  data = Array.make size dummy;
  size;
}

let push buffer elem =
  let k = buffer.pos + buffer.count in
  buffer.data.(if k < buffer.size then k else 0) <- elem;
  if buffer.count < buffer.size then
    buffer.count <- buffer.count + 1
  else
    buffer.pos <- buffer.pos + 1;
  ()

let pop buffer =
  if buffer.count = 0 then raise Not_found;
  let result = buffer.data.(buffer.pos) in
  (* if you want to free the buffer content, buffer.data.(pos) <- dummy *)
  let pos' = buffer.pos + 1 in
  buffer.pos <- (if pos' < buffer.size then pos' else 0);
  buffer.count <- buffer.count - 1;
  result

(* test *)
let () =
  let buf = create 2 '0' in
  (* *)
  push buf '1';
  (* 1 *)
  push buf '2';
  (* 1 2 *)
  push buf '3';
  (*   2 3 *)
  assert (pop buf = '2');
  (*     3 *)
  push buf '4';
  (*     3 4 *)
  assert (pop buf = '3');
  (*       4 *)
  assert (pop buf = '4');
  (*         *)
  assert (try ignore (pop buf); false with Not_found -> true);
  assert (try ignore (pop buf); false with Not_found -> true);


On Mon, Apr 2, 2012 at 5:04 PM, David Allsopp <dra-news@metastack.com> wrote:
> Hongbo Zhang wrote:
>> Hi List,
>>     I want to implement sliding window algorithm (in place, no memory
>> copy), I wonder whether I need to write c code.
>>
>>     To make it clear and simple,
>>        In c, you can record the head pointer of the array, and do the
>> modulo operations when get and set
>>        In ocaml, it seems you have an array a of type int array,  you can
>> not do things like this *(&a+5).
>
> Perhaps I'm missing something, but if you're planning on using arrays, what's wrong with retrieving the item using the array index modulo the length of the array?
>
> i.e.
>
> let a = [| ... or whatever ... |] in
> a.(5 mod Array.length a)
>
> If accessing an array by index instead of by pointer worries you, then you're looking at the wrong language ;o)
>
>
> David
>
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

Re: [Caml-list] How could I implement an efficient ring buffer?

[Benedikt Grundmann]

Use core's Dequeue module.

Cheers,

Bene

On 2 April 2012 15:31, Hongbo Zhang <bobzhang1988@gmail.com> wrote:
> Hi List,
>   I want to implement sliding window algorithm (in place, no memory copy), I
> wonder whether I need to write c code.
>
>   To make it clear and simple,
>      In c, you can record the head pointer of the array, and do the modulo
> operations when get and set
>      In ocaml, it seems you have an array a of type int array,  you can not
> do things like this *(&a+5).
>   Many thanks
>
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>



-- 
Calvin: I try to make everyone's day a little more
surreal.

(From Calvin & Hobbes)

RE: [Caml-list] How could I implement an efficient ring buffer?

[Jon Harrop]

The "mod" and the write barrier will significantly degrade performance vs C.
Probably faster to replace "mod" with if-based wrap around but there's
nothing you can do about the write barrier.

Cheers,
Jon.

> -----Original Message-----
> From: David Allsopp [mailto:dra-news@metastack.com]
> Sent: 02 April 2012 16:05
> To: Hongbo Zhang; Caml List
> Subject: RE: [Caml-list] How could I implement an efficient ring buffer?
> 
> Hongbo Zhang wrote:
> > Hi List,
> >     I want to implement sliding window algorithm (in place, no memory
> > copy), I wonder whether I need to write c code.
> >
> >     To make it clear and simple,
> >        In c, you can record the head pointer of the array, and do the
> > modulo operations when get and set
> >        In ocaml, it seems you have an array a of type int array,  you
> > can not do things like this *(&a+5).
> 
> Perhaps I'm missing something, but if you're planning on using arrays,
what's
> wrong with retrieving the item using the array index modulo the length of
the
> array?
> 
> i.e.
> 
> let a = [| ... or whatever ... |] in
> a.(5 mod Array.length a)
> 
> If accessing an array by index instead of by pointer worries you, then
you're
> looking at the wrong language ;o)
> 
> 
> David
> 
> 
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

Re: [Caml-list] How could I implement an efficient ring buffer?

[Francois Berenger]

On 04/02/2012 11:31 PM, Hongbo Zhang wrote:
> Hi List,
> I want to implement sliding window algorithm (in place, no memory copy),
> I wonder whether I need to write c code.

Queues are described in Chris Okasaki's book, with a functional 
implementation in all senses of the term.

If you don't want to roll your own, someone suggested Janestreet's 
core's Dequeue module and Gabriel sent you some implementation.

Regards,
F.

> To make it clear and simple,
> In c, you can record the head pointer of the array, and do the modulo
> operations when get and set
> In ocaml, it seems you have an array a of type int array, you can not do
> things like this *(&a+5).
> Many thanks
>
>