A question about how to remove the first element of slice

[Shafreeck Sea]

Hi guys:

My workmate was confused when he was viewing the source code of src/database/sql/sql.go about removing the first element of a slice. He show us the code in our internal group and we some guys knowing about golang talked about this, unfortunately, we all have no ideas about this.

It is in the function "putConnDBLocked", here is the code snippet:

        req := db.connRequests[0]

        // This copy is O(n) but in practice faster than a linked list.

        // TODO: consider compacting it down less often and

        // moving the base instead?

        copy(db.connRequests, db.connRequests[1:])

        db.connRequests = db.connRequests[:c-1]

The operation is to remove db.connRequests[0]. But it use a more complicated way: first copy all elements except the first one to db.connRequests and then remove the last element.

Why not using a more simple way:

    db.connRequests = db.connRequests[1:]

The comment "This copy is O(n) but in practice faster than a linked list" here is also confusing. I did not know why mentions the linked list. I finally found it out by using git blame and following the commit message and found this: https://codereview.appspot.com/107020044/patch/100001/110001 . Then I got that it was a linked list before .

However the "TODO" in the comment really traps me.  I think this maybe the key that let me know why not using "db.connRequests = db.connRequests[1:]".

Do you guys have any ideas ?

[James Bardin]

On Friday, September 11, 2015 at 8:27:42 AM UTC-4, Shafreeck Sea wrote:

Hi guys:

My workmate was confused when he was viewing the source code of src/database/sql/sql.go about removing the first element of a slice. He show us the code in our internal group and we some guys knowing about golang talked about this, unfortunately, we all have no ideas about this.

It is in the function "putConnDBLocked", here is the code snippet:

        req := db.connRequests[0]

        // This copy is O(n) but in practice faster than a linked list.

        // TODO: consider compacting it down less often and

        // moving the base instead?

        copy(db.connRequests, db.connRequests[1:])

        db.connRequests = db.connRequests[:c-1]

The operation is to remove db.connRequests[0]. But it use a more complicated way: first copy all elements except the first one to db.connRequests and then remove the last element.

Why not using a more simple way:

    db.connRequests = db.connRequests[1:]

This leaves the first element of the underlying slice inaccessible. If this is continually done, along with more appends, the slice array would continue to grow. Moving the empty space to the end allows another element to be efficiently appended, and doesn't waste any space.

 

The comment "This copy is O(n) but in practice faster than a linked list" here is also confusing. I did not know why mentions the linked list. I finally found it out by using git blame and following the commit message and found this: https://codereview.appspot.com/107020044/patch/100001/110001 . Then I got that it was a linked list before .

 

However the "TODO" in the comment really traps me.  I think this maybe the key that let me know why not using "db.connRequests = db.connRequests[1:]".

 The TODO is to essentially use the method you're suggesting, and only occasionally do the full copy back to the head of the array.

[Nick Craig-Wood]

On 11/09/15 13:38, James Bardin wrote:
> On Friday, September 11, 2015 at 8:27:42 AM UTC-4, Shafreeck Sea wrote:
> Why not using a more simple way:
> db.connRequests = db.connRequests[1:]
>
> This leaves the first element of the underlying slice inaccessible. If
> this is continually done, along with more appends, the slice array would
> continue to grow.

That isn't actually true.

If there are appends, then sooner or later one of them will trigger a
re-allocation, the slice data will be copied and the empty space at the
front will be reclaimed.

--
Nick Craig-Wood <ni...@craig-wood.com> -- http://www.craig-wood.com/nick

[James Bardin]

On Fri, Sep 11, 2015 at 9:24 AM, Nick Craig-Wood <ni...@craig-wood.com> wrote:
> On 11/09/15 13:38, James Bardin wrote:
>> On Friday, September 11, 2015 at 8:27:42 AM UTC-4, Shafreeck Sea wrote:
>> Why not using a more simple way:
>> db.connRequests = db.connRequests[1:]
>>
>> This leaves the first element of the underlying slice inaccessible. If
>> this is continually done, along with more appends, the slice array would
>> continue to grow.
>
> That isn't actually true.
>
> If there are appends, then sooner or later one of them will trigger a
> re-allocation, the slice data will be copied and the empty space at the
> front will be reclaimed.
>

Yes, sorry, mis-spoke here. It wouldn't grow, it could just wast the
space in the current array.

[Shafreeck Sea]

@Nick @James Got it , very appreciated !