From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by sympa.inria.fr (Postfix) with ESMTPS id 25F907EE99 for ; Mon, 20 Jan 2014 09:47:50 +0100 (CET) Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of mshinwell@janestreet.com) identity=pra; client-ip=38.105.200.229; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="mshinwell@janestreet.com"; x-sender="mshinwell@janestreet.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail3-smtp-sop.national.inria.fr: domain of mshinwell@janestreet.com designates 38.105.200.229 as permitted sender) identity=mailfrom; client-ip=38.105.200.229; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="mshinwell@janestreet.com"; x-sender="mshinwell@janestreet.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@tot-dmz-mxout1.janestreet.com) identity=helo; client-ip=38.105.200.229; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="mshinwell@janestreet.com"; x-sender="postmaster@tot-dmz-mxout1.janestreet.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Aq8BAD/i3FImacjlnGdsb2JhbABZhBm7PYEBHg4BAQEBAQYWCTyCJQEBAQQnGQEBNwEPCwsNLiEBEgEFARwGEwiHaQMRAwKbZYsThFIBBZIZDYVWEQaMa4EobAeEOJY6gWyMXYNOGCmEWYFx X-IPAS-Result: Aq8BAD/i3FImacjlnGdsb2JhbABZhBm7PYEBHg4BAQEBAQYWCTyCJQEBAQQnGQEBNwEPCwsNLiEBEgEFARwGEwiHaQMRAwKbZYsThFIBBZIZDYVWEQaMa4EobAeEOJY6gWyMXYNOGCmEWYFx X-IronPort-AV: E=Sophos;i="4.95,689,1384297200"; d="scan'208";a="45390247" Received: from mx5.janestreet.com (HELO tot-dmz-mxout1.janestreet.com) ([38.105.200.229]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 20 Jan 2014 09:47:49 +0100 Received: from tot-oib-smtp1.delacy.com ([172.27.22.15] helo=tot-smtp) by tot-dmz-mxout1.janestreet.com with esmtp (Exim 4.76) (envelope-from ) id 1W5AWI-0007Xu-7J for caml-list@inria.fr; Mon, 20 Jan 2014 03:47:46 -0500 Received: from tot-dmz-mxgoog1.delacy.com ([172.27.224.14] helo=mxgoog2.janestreet.com) by tot-smtp with esmtps (TLSv1:AES256-SHA:256) (Exim 4.72) (envelope-from ) id 1W5AWI-0005iz-6L for caml-list@inria.fr; Mon, 20 Jan 2014 03:47:46 -0500 Received: from mail-vc0-f169.google.com ([209.85.220.169]) by mxgoog2.janestreet.com with esmtp (Exim 4.76) (envelope-from ) id 1W5AWI-0002xa-42 for caml-list@inria.fr; Mon, 20 Jan 2014 03:47:46 -0500 Received: by mail-vc0-f169.google.com with SMTP id hq11so2718458vcb.0 for ; Mon, 20 Jan 2014 00:47:46 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=janestreet.com; s=google; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=ErehW2t9q6kMY4ca0nTLzupPc5qbqJyMDDvUW+5uBoQ=; b=AQcIh2O9XWGkEk0SpvP5AYRioAnEwI0DBp++fRYH/ns3UmPURkvQJPNM/juZIwt3t3 +meKrTSO2w3n1EwsnoEa8566EihecSq+yeIP2fyVxLuKaH/45KqJqbRTEou1J/Lx1cr5 eLzLwCe5Ll4G1g1OYS6kwTcn13vU7U5/wR08s= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc:content-type; bh=ErehW2t9q6kMY4ca0nTLzupPc5qbqJyMDDvUW+5uBoQ=; b=MBkQA1OYYwDuh5rZWnDsP8OgdEn2Hc7fLWz/gxgf4uaPVvsF9OwpuDweOePURNNfj5 emLjVuyVmPPkRLj7hC9ERHzihSLG/cVLYL3Bc2+LvjMvGyITTE6QScMjjcqzBBvZhwNi sVi5F45u1xYbJXxra7ovNo7USZjm7IhgCiEOimvsjFke56v5cmJvKDWsaDnKeydZCBeu kWl7BoFe9S7jXfKo5ZgXPEIddh/AYAOVAHgUCWGE3F7j4UgLyHUI7dLportmoRYylpgF vX06Pfcgf+JMl0sxAbAAAMqoC1JcXU15Hs5SGH1hyuxzzXJ8z7dkOoumoRThE1FlN9qn yBMg== X-Gm-Message-State: ALoCoQkq9dh6/6kYUneP3JihtmET8ZTfNyBVvQQtSo4QnVhaBfthKQgcK1qlol1xr0yLNLt1jJE8l7S8elDJdaaLWn/i7RYm+3/zxQmpqbgH+6gwcOHg5UUVvJl/j8H09J8uMBpfkglYKP/pHS/zUxBWgr7FB9aAMQ== X-Received: by 10.221.66.73 with SMTP id xp9mr283780vcb.27.1390207665992; Mon, 20 Jan 2014 00:47:45 -0800 (PST) MIME-Version: 1.0 X-Received: by 10.221.66.73 with SMTP id xp9mr283773vcb.27.1390207665908; Mon, 20 Jan 2014 00:47:45 -0800 (PST) Received: by 10.58.152.106 with HTTP; Mon, 20 Jan 2014 00:47:45 -0800 (PST) In-Reply-To: References: Date: Mon, 20 Jan 2014 08:47:45 +0000 Message-ID: From: Mark Shinwell To: Bob Atkey Cc: "caml-list@inria.fr" Content-Type: text/plain; charset=ISO-8859-1 X-Validation-by: mshinwell@janestreet.com Subject: Re: [Caml-list] ANN: unboxed-arrays-0.1: Unboxed arrays for OCaml On 19 January 2014 18:01, Bob Atkey wrote: > The runtime representation of OCaml arrays usually stores the elements > using a 'boxed' representation, meaning that if the value of a > particular element cannot be stored within a single machine word > (i.e., it is not an argument-less constructor or an `int` value), then > the array actually contains a pointer to the representation of the > element elsewhere in the heap. (Note that `float` arrays are special > cased.) This boxing representation leads to an extra indirection when > accessing elements of the array, means that memory is wasted, and > decreases data locality, to the detriment of efficent cache usage. Thanks for sharing your code. I also did an experiment with this recently (although I would argue that it isn't always clear that flat arrays are desirable). My flat array module is designed to hold a sequence of values of record type. Pointers to the records may be retrieved and then normal mutable field updates may be used to change them. (In case you are wondering, if you put some other variety of value in the array, then it's probably safe but won't be useful---since in particular there is no "set" method provided.) module Flat_array : sig type 'a t val create : num_elements:int -> default:'a -> 'a t val element_at : 'a t -> index:int -> 'a end Here's a simple example of its use. The code of the implementation is left as an interesting exercise for the reader ;) type t = { mutable foo : int; mutable bar : string; } let default = { foo = 42; bar = "hello world"; } let test () = let arr = Flat_array.create ~num_elements:10 ~default in let r = Flat_array.element_at arr ~index:4 in Printf.printf "foo=%d, bar=%s\n%!" r.foo r.bar; Gc.compact (); (* make sure we haven't corrupted the heap *) r.foo <- 10; r.bar <- "bar"; Gc.compact (); Printf.printf "foo=%d, bar=%s\n%!" r.foo r.bar -- module Flat_array : sig type 'a t val create : num_elements:int -> default:'a -> 'a t val element_at : 'a t -> index:int -> 'a end = struct type _ t = Obj.t let create ~num_elements ~default = let fields_per_elt = Obj.size (Obj.repr default) in let size = 1 + num_elements * (1 + fields_per_elt) - 1 in let t = Obj.new_block Obj.closure_tag size in let stride = Sys.word_size/8 * (fields_per_elt + 1) in Obj.set_field t (size - 1) (Obj.repr stride); let default = Obj.repr default in for elt = 0 to num_elements - 1 do let header_index_for_elt = (1 + fields_per_elt) * elt - 1 in for field = 0 to fields_per_elt - 1 do Obj.set_field t (header_index_for_elt + 1 + field) (Obj.field default field) done; if elt > 0 then begin let infix_header = let infix_offset = elt * (fields_per_elt + 1) in let actual_value = (infix_offset lsl 10) lor Obj.infix_tag in assert (actual_value land 1 = 1); actual_value lsr 1 in Obj.set_field t header_index_for_elt (Obj.repr infix_header) end done; t let element_at t ~index = let offset = if index = 0 then 0 else let t = ((Obj.magic t) : int array) in let stride = t.(Array.length t - 1) in stride * index in let record_is_at = Obj.add_offset t (Int32.of_int offset) in Obj.obj record_is_at end