Received: by 10.66.85.137 with SMTP id h9mr8666469paz.16.1351311209984;
        Fri, 26 Oct 2012 21:13:29 -0700 (PDT)
X-BeenThere: scala-user@googlegroups.com
Received: by 10.68.223.67 with SMTP id qs3ls18384594pbc.8.gmail; Fri, 26 Oct
 2012 21:13:26 -0700 (PDT)
Received: by 10.68.223.98 with SMTP id qt2mr7939509pbc.20.1351311206161;
        Fri, 26 Oct 2012 21:13:26 -0700 (PDT)
Date: Fri, 26 Oct 2012 21:13:25 -0700 (PDT)
From: "Russ P." <russ.paie...@gmail.com>
To: scala-user@googlegroups.com
Cc: "Russ P." <russ.paie...@gmail.com>
Message-Id: <3abf023c-ff35-403c-9cac-f59b3456ceb3@googlegroups.com>
In-Reply-To: <CAHyB3VW1m0UhxESBmG3ngDFBSu_ctwhA44w-qZT-ED7gjpSvQA@mail.gmail.com>
References: <846afeae-733f-42f9-827a-92cdb01b8177@googlegroups.com>
 <CAHyB3VW1m0UhxESBmG3ngDFBSu_ctwhA44w-qZT-ED7gjpSvQA@mail.gmail.com>
Subject: Re: [scala-user] appending to a Vector
MIME-Version: 1.0
Content-Type: multipart/mixed; 
	boundary="----=_Part_1082_2080524.1351311205515"

------=_Part_1082_2080524.1351311205515
Content-Type: multipart/alternative; 
	boundary="----=_Part_1083_3665022.1351311205515"

------=_Part_1083_3665022.1351311205515
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit



On Friday, October 26, 2012 5:58:55 PM UTC-7, Daniel Sobral wrote:
>
> On Fri, Oct 26, 2012 at 4:51 PM, Russ P. <russ.p...@gmail.com<javascript:>> 
> wrote: 
> > In one of Martin's coursera lectures for this week, he discusses 
> appending 
> > an element to a Vector. Please correct me if I am wrong, but that does 
> not 
> > appear to be an efficient operation that one would want to do many times 
> to 
> > build a Vector. Also, the resulting Vector does not appear to have the 
> same 
> > form as one would expect. Did I understand correctly that simply 
> appending a 
> > single element always adds an array of length 32? I hope not! 
> > 
> > A while back I discovered and started using a class called 
> VectorBuilder, 
> > which I assume is a more efficient way to build a Vector. Perhaps Martin 
> > should have mentioned it in his lecture. 
>
> It does create at least one array of length 32, and possibly up to 6, 
> as would any update operation. But, here's the kick: because of the 
> bad locality of common lists, creating an array of 32 elements and 
> creating a single cons have about the same cost compared to the cache 
> miss. The vector then gains performance back because of locality of 
> reference on reads. 
>
> OK, let me see if I have this straight. Let's say I create a Vector of one 
element. Then I append another element to it. Are you saying that another 
array of length 32 is created to accommodate the new element? I'm just 
trying to understand. Thanks.

--Russ P.

------=_Part_1083_3665022.1351311205515
Content-Type: text/html; charset=utf-8
Content-Transfer-Encoding: 7bit

<br><br>On Friday, October 26, 2012 5:58:55 PM UTC-7, Daniel Sobral wrote:<blockquote class="gmail_quote" style="margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">On Fri, Oct 26, 2012 at 4:51 PM, Russ P. &lt;<a href="javascript:" target="_blank" gdf-obfuscated-mailto="xxEr9WE9QQEJ">russ.p...@gmail.com</a>&gt; wrote:
<br>&gt; In one of Martin's coursera lectures for this week, he discusses appending
<br>&gt; an element to a Vector. Please correct me if I am wrong, but that does not
<br>&gt; appear to be an efficient operation that one would want to do many times to
<br>&gt; build a Vector. Also, the resulting Vector does not appear to have the same
<br>&gt; form as one would expect. Did I understand correctly that simply appending a
<br>&gt; single element always adds an array of length 32? I hope not!
<br>&gt;
<br>&gt; A while back I discovered and started using a class called VectorBuilder,
<br>&gt; which I assume is a more efficient way to build a Vector. Perhaps Martin
<br>&gt; should have mentioned it in his lecture.
<br>
<br>It does create at least one array of length 32, and possibly up to 6,
<br>as would any update operation. But, here's the kick: because of the
<br>bad locality of common lists, creating an array of 32 elements and
<br>creating a single cons have about the same cost compared to the cache
<br>miss. The vector then gains performance back because of locality of
<br>reference on reads.
<br><br></blockquote><div>OK, let me see if I have this straight. Let's say I create a Vector of one element. Then I append another element to it. Are you saying that another array of length 32 is created to&nbsp;accommodate&nbsp;the new element? I'm just trying to understand. Thanks.</div><div><br></div><div>--Russ P.</div>
------=_Part_1083_3665022.1351311205515--

------=_Part_1082_2080524.1351311205515--