Re: [squid-dev] [PATCH] Extend SBufContainerJoin to have prefix and suffix arguments

[Alex Rousskov]

On 11/11/2016 01:30 AM, Kinkie wrote:
> On Fri, Nov 11, 2016 at 5:02 AM, Amos Jeffries  wrote:
>> On 11/11/2016 9:28 a.m., Kinkie wrote:
>>>
>>> v4 attached.
>>>
>>
>> Does it have to take begin() and end() iterators explicitly?
>>  can we not have it take the container itself and use a for(auto  :
>> container) loop ?
> 
> No it doesn't but it's sometimes convenient.
> My use case is the regex-compressing code. It can be reduced to (pseudocode)
> 
> join(regex-so-far, wordsList., separator=")|(", prefix="(", suffix=")")
> 
> granted, it can be done with explicit append calls but then you can't
> inline it (e.g in streams).
> 
> The code used to take the whole container, but there's a use case for
> iterating over a slice only.

Accepting iterators is standard in STL (despite being slightly
inconvenient) probably because accepting iterators covers a lot more
potential use cases.

Alex.

___
squid-dev mailing list
squid-dev@lists.squid-cache.org
http://lists.squid-cache.org/listinfo/squid-dev

Re: [squid-dev] [PATCH] Extend SBufContainerJoin to have prefix and suffix arguments

[Kinkie]

On Fri, Nov 11, 2016 at 5:02 AM, Amos Jeffries  wrote:
> On 11/11/2016 9:28 a.m., Kinkie wrote:
>>
>> v4 attached.
>>
>
> Does it have to take begin() and end() iterators explicitly?
>  can we not have it take the container itself and use a for(auto  :
> container) loop ?

No it doesn't but it's sometimes convenient.
My use case is the regex-compressing code. It can be reduced to (pseudocode)

join(regex-so-far, wordsList., separator=")|(", prefix="(", suffix=")")

granted, it can be done with explicit append calls but then you can't
inline it (e.g in streams).

The code used to take the whole container, but there's a use case for
iterating over a slice only.

-- 
Francesco
___
squid-dev mailing list
squid-dev@lists.squid-cache.org
http://lists.squid-cache.org/listinfo/squid-dev

Re: [squid-dev] [PATCH] Extend SBufContainerJoin to have prefix and suffix arguments

[Amos Jeffries]

On 11/11/2016 9:28 a.m., Kinkie wrote:
> 
> v4 attached.
> 

Does it have to take begin() and end() iterators explicitly?
 can we not have it take the container itself and use a for(auto  :
container) loop ?

Amos

___
squid-dev mailing list
squid-dev@lists.squid-cache.org
http://lists.squid-cache.org/listinfo/squid-dev

Re: [squid-dev] [PATCH] Extend SBufContainerJoin to have prefix and suffix arguments

[Kinkie]

> Tests and code analysis show that JoinContainerIntoSBuf() allocates when
> no allocation is needed. I have also shown that it is possible to
> implement JoinContainerIntoSBuf() so that there is no extra allocation.
> AFAICT, going forward, you choices are:
>
> * state that the extra allocation is not your fault, leaving it as is,
>   and/or
> * fix JoinContainerIntoSBuf() to avoid the extra allocation.
>
> When you added the "dest" parameter, you have started moving in the
> latter direction.

I'm completing that by using the reseve() based approach

>> At the same time, it's not a matter of API: the extended
>> reserve() has the same behavior as the "problem" is elsewhere.
>
> Whether SBuf::reserve() has the same behavior as reserveSpace() depends
> on reserve() configuration parameters.
>
> JoinContainerIntoSBuf() should configure reserve() in such a way that
> reserve() does _not_ have the same behavior as reserveSpace(). I showed
> how to do that in JoinContainerIntoSBuf4() in my earlier patch. The
> patch attached now has an even simpler JoinContainerIntoSBuf5()
> implementation because I fixed reserve() to not require the .ideal
> configuration parameter to be set (trunk r14917).

Aha! I was confused as I had branched off earlier. Merging.

>
>> What we could do is:
>> - define a reserveMinSpace() which does not shrink storage
>
> Having two methods called reserveMinSpace() and reserveSpace(), one of
> which does not shrink and the other one does, makes no sense to me
> because the method names do not reflect that difference at all and
> because reserve() is always primarily about "minimum" space anyway.
>
> More importantly, reserveSpace() guarantees single ownership. IMO,
> shrinking is essentially a side effect of that guarantee.

Yes.

> I suspect we do not need a "provide single-ownership space, shrinking
> the existing single-owned MemBlob if there is one" method, but if you
> have some existing use cases for it, please share them. If there are no
> such cases, reserveSpace()/reserveCapacity() should be optimized to
> avoid unnecessary re-allocation when their MemBlob is already not
> shared, but that is a different story, unrelated to JoinContainerIntoSBuf!

I agree. And that's why I think they could be simply convenience
methods for reserve().

>> - reimplement [...] reserveSpace() as convenience wrapper around reserve()
>
> Sure, but that is outside this patch scope.

Yes.


>> - while we're at it, give SBufReservationRequirements a convenience 
>> constructor
>
> With minSpace as the only parameter? Sure. Please do not forget
> "explicit". Again, that seems to be outside your patch scope.

Yes.

> I do not recommend providing more than one constructor parameter though
> because constructors with multiple same- or similar-type parameters are
> a recipe for mismatching parameters disasters.

Let's optimize the common case, we'll see if there is a need for more later on.

v4 attached.

-- 
Francesco


sbufcontainerjoin-v4.patch
Description: Binary data
___
squid-dev mailing list
squid-dev@lists.squid-cache.org
http://lists.squid-cache.org/listinfo/squid-dev

Re: [squid-dev] [PATCH] Extend SBufContainerJoin to have prefix and suffix arguments

[Alex Rousskov]

On 11/06/2016 01:15 AM, Kinkie wrote:
>>> +dest.reserveSpace(prefix.length() + totalContainerSize + 
>>> suffix.length());
>>
>> Please note that v4 still allocates memory according to my last
>> experiment. See JoinContainerIntoSBuf3() which mimics your patch v4. You
>> may claim that the unnecessary allocation is not the fault of this
>> patch, and you could be right, but I was hoping this observation will
>> inspire you to change
> 
> I don't follow. The space requirement in JoinContainerIntoSBuf is not
> advisory. The accumulate at the beginning of the function is meant to
> calculate exactly how much space is needed, to copy (if needed) only
> once and early.

What you say is true except for the "if needed" part. In some cases,
JoinContainerIntoSBuf() allocates and copies without needed. Those extra
allocations are present in v1, v2, v3, and v4 versions of the patch, but
the reasons behind those unnecessary allocations varied.


> The traces you provided do not reallocate there because the underlying
> MemBlob has grown enough in previous calls to have enough free space
> to cover the projected needs (it was resized last at
> JoinContainerIntoSBuf3).

No, "has grown enough" is not the reason why JoinContainerIntoSBuf4()
does not reallocate needlessly.


> In other words, the test data is dirtied as the tests progress.

My tests were indeed dirty (sorry) and could have easily led to wrong
conclusions, but they did not. The cleaned up version (attached) shows
exactly the same problem, this time without any effect of earlier tests
on later tests.


> This is correct behavior: the code advises that it only needs that
> much storage and the SBuf shrinks.

Violating explicit STL reserve() guarantees is rarely a good idea but,
for now, I will not argue about what reserveSpace() should do. I will
focus on JoinContainerIntoSBuf() instead.

Tests and code analysis show that JoinContainerIntoSBuf() allocates when
no allocation is needed. I have also shown that it is possible to
implement JoinContainerIntoSBuf() so that there is no extra allocation.
AFAICT, going forward, you choices are:

* state that the extra allocation is not your fault, leaving it as is,
  and/or
* fix JoinContainerIntoSBuf() to avoid the extra allocation.

When you added the "dest" parameter, you have started moving in the
latter direction.


> As a demonstration, swapping order of tests 3 and 4 results in:

[Snipped wrong conclusions based on confusing dirty tests.
 See cleaned up order-independent tests instead.]


> At the same time, it's not a matter of API: the extended
> reserve() has the same behavior as the "problem" is elsewhere.

Whether SBuf::reserve() has the same behavior as reserveSpace() depends
on reserve() configuration parameters.

JoinContainerIntoSBuf() should configure reserve() in such a way that
reserve() does _not_ have the same behavior as reserveSpace(). I showed
how to do that in JoinContainerIntoSBuf4() in my earlier patch. The
patch attached now has an even simpler JoinContainerIntoSBuf5()
implementation because I fixed reserve() to not require the .ideal
configuration parameter to be set (trunk r14917).



> What we could do is:
> - define a reserveMinSpace() which does not shrink storage

Having two methods called reserveMinSpace() and reserveSpace(), one of
which does not shrink and the other one does, makes no sense to me
because the method names do not reflect that difference at all and
because reserve() is always primarily about "minimum" space anyway.

More importantly, reserveSpace() guarantees single ownership. IMO,
shrinking is essentially a side effect of that guarantee.

I suspect we do not need a "provide single-ownership space, shrinking
the existing single-owned MemBlob if there is one" method, but if you
have some existing use cases for it, please share them. If there are no
such cases, reserveSpace()/reserveCapacity() should be optimized to
avoid unnecessary re-allocation when their MemBlob is already not
shared, but that is a different story, unrelated to JoinContainerIntoSBuf!


> - reimplement [...] reserveSpace() as convenience wrapper around reserve()

Sure, but that is outside this patch scope.


> - while we're at it, give SBufReservationRequirements a convenience 
> constructor

With minSpace as the only parameter? Sure. Please do not forget
"explicit". Again, that seems to be outside your patch scope.

I do not recommend providing more than one constructor parameter though
because constructors with multiple same- or similar-type parameters are
a recipe for mismatching parameters disasters.


HTH,

Alex.

Testing allocations in various JoinContainerIntoSBuf() implementations.

This version makes each test case independent from other test cases.

Also added JoinContainerIntoSBuf5() that uses trunk r14917 to provide a
simpler allocation-free implementation.

=== modified file 'src/AccessLogEntry.cc'
--- src/AccessLogEntry.cc	2016-10-28 11:55:44 +
+++ src/AccessLogEntry.cc	

Re: [squid-dev] [PATCH] Extend SBufContainerJoin to have prefix and suffix arguments

[Kinkie]

>> +dest.reserveSpace(prefix.length() + totalContainerSize + 
>> suffix.length());
>
> Please note that v4 still allocates memory according to my last
> experiment. See JoinContainerIntoSBuf3() which mimics your patch v4. You
> may claim that the unnecessary allocation is not the fault of this
> patch, and you could be right, but I was hoping this observation will
> inspire you to change

I don't follow. The space requirement in JoinContainerIntoSBuf is not
advisory. The accumulate at the beginning of the function is meant to
calculate exactly how much space is needed, to copy (if needed) only
once and early.

> * either your patch (mimicking my JoinContainerIntoSBuf4() which does
> not result in extra allocation) reserveSpace()

The traces you provided do not reallocate there because the underlying
MemBlob has grown enough in previous calls to have enough free space
to cover the projected needs (it was resized last at
JoinContainerIntoSBuf3).

In other words, the test data is dirtied as the tests progress.
Follow with me:
2016/11/04 11:47:21.841| 24,8| SBuf.cc(42) SBuf: SBuf2698 created
2016/11/04 11:47:21.841| 24,8| SBuf.cc(908) cow: SBuf2698 new size:1024
2016/11/04 11:47:21.841| 24,8| SBuf.cc(878) reAlloc: SBuf2698 new size: 1024

But then:

2016/11/04 11:47:21.841| 1,2| AccessLogEntry.cc(47)
JoinContainerIntoSBuf2: started
2016/11/04 11:47:21.841| 1,2| AccessLogEntry.cc(48)
JoinContainerIntoSBuf2: did not create an empty buf
2016/11/04 11:47:21.841| 24,8| SBuf.cc(908) cow: SBuf2698 new size:124
2016/11/04 11:47:21.841| 24,8| SBuf.cc(878) reAlloc: SBuf2698 new size: 124

This is correct behavior: the code advises that it only needs that
much storage and the SBuf shrinks. It's passed by reference, so from
now on 'buffer' has 124 bytes of storage instead of the pre-allocated
1024.

As a demonstration, swapping order of tests 3 and 4 results in:
[...]
2016/11/06 07:05:47.860 kid1| 1,2| main.cc(457) JoinContainerIntoSBuf4: started
2016/11/06 07:05:47.860 kid1| 24,8| SBuf.cc(130) reserve: SBuf3657
was: 0+81+47=128
2016/11/06 07:05:47.860 kid1| 24,8| SBuf.cc(912) cow: SBuf3657 new size:181
2016/11/06 07:05:47.860 kid1| 24,8| SBuf.cc(882) reAlloc: SBuf3657 new size: 181
2016/11/06 07:05:47.860 kid1| 24,8| MemBlob.cc(101) memAlloc: blob2420
memAlloc: requested=181, received=512
2016/11/06 07:05:47.860 kid1| 24,7| SBuf.cc(891) reAlloc: SBuf3657 new
store capacity: 512
2016/11/06 07:05:47.860 kid1| 24,7| SBuf.cc(146) reserve: SBuf3657
now: 0+81+431=512
2016/11/06 07:05:47.860 kid1| 1,2| main.cc(462)
JoinContainerIntoSBuf4: reserved space
2016/11/06 07:05:47.860 kid1| 24,7| SBuf.cc(154) rawSpace: reserving 7
for SBuf3657
2016/11/06 07:05:47.860 kid1| 24,7| SBuf.cc(161) rawSpace: SBuf3657 not growing


I don't think however that we should change reserveSpace() behavior
not to ever shrink; there may be use cases where it's better not to do
it in fact. At the same time, it's not a matter of API: the extended
reserve() has the same behavior as the "problem" is elsewhere.

>
> * or reserveSpace() (after making sure that all callers are going to be
> OK with that change).
>
> The latter would be better if it is possible. If it is not possible,
> then we may need to change reserveSpace() documentation so that folks do
> not use that method like you did.

What we could do is:
- define a reserveMinSpace() which does not shrink storage
- reimplement both reserveSpace() and reserveMinSpace() as convenience
wrappers around reserve() which is undoubtably more powerful
- while we're at it, give SBufReservationRequirements a convenience constructor

What do you think?
Thanks.

-- 
Francesco
___
squid-dev mailing list
squid-dev@lists.squid-cache.org
http://lists.squid-cache.org/listinfo/squid-dev

Re: [squid-dev] [PATCH] Extend SBufContainerJoin to have prefix and suffix arguments

[Kinkie]

On Fri, Nov 4, 2016 at 6:12 PM, Alex Rousskov
 wrote:
> On 11/04/2016 01:12 AM, Kinkie wrote:
>> On Thu, Nov 3, 2016 at 10:55 PM, Alex Rousskov
>>  wrote:
>>> On 11/03/2016 03:19 PM, Kinkie wrote:
 On Tue, Nov 1, 2016 at 8:47 PM, Alex Rousskov wrote:
> On 11/01/2016 02:02 PM, Kinkie wrote:
>>   the attached patch extends SBufContainerJoin to have prefix and
>> suffix arguments.
>>>
> I recommend reworking this by adding a dest parameter:
> SBuf (SBuf , ...);
>
>> attached v3 does this.
>
>>  SBuf
>> +JoinContainerIntoSBuf(SBuf , ...
>
> Please return dest, not a copy of it. There is no reason to create and
> destroy a new SBuf object here IMO. SBuf creation and destruction are
> not as expensive as underlying storage copying, but they are still a
> measurable expense without justification AFAICT.

Doh, right. I had actually thought about this after sending the patch.

> There are certainly many cases where using references is a bad idea but
> returning a fed-by-reference "dest" is not one of them AFAICT. In fact,
> it is nearly the norm in "chainable" calls such as those that append
> something.

I agree that this case fits perfectly.

>> +/// variant of JoinContainerIntoSBuf not needing a SBuf lvalue
>
> I recommend a more informative description than retelling of the
> function declaration code. For example:
>
> /// convenience JoinContainerIntoSBuf() wrapper with an extra memory
> allocation

The extra memory allocation is a side effect; I agree it is a
convenience, but the convenience is in not needing a SBuf lvalue. This
makes it useable e.g. in ostreams

>
>> +dest.reserveSpace(sz + prefix.length() + suffix.length());
>
> I would reorder the operands to make the code more self-documenting,
> especially when using an anonymous variable name like "sz":
>
>   dest.reserveSpace(prefix.length() + sz + suffix.length());

Ok. I'm also renaming sz for extra clarity.

>
>
>> I am not generally worried as it seems you are about copying SBufs as
>> long as the underlying storage is not reallocated needlessly.
>
> Unfortunately, all three patch versions reallocate storage needlessly
> (for various reasons). You can study the attached debugging from the
> attached patch to see what is actually going on in various
> JoinContainerIntoSBuf implementations. It may surprise and inspire you
> to make the code better. It did surprise and inspire me (but I wish I
> was not doing this legwork!).

Sorry about that causing extra work for you.

Updated patch attached. I'm struggling a bit with the convenience
wrapper documentation. Note that the wrapper cannot return a ref,
intentionally so. I hope RVO will optimize that cost away as much as
possible.

-- 
Francesco


sbufcontainerjoin-v4.patch
Description: Binary data
___
squid-dev mailing list
squid-dev@lists.squid-cache.org
http://lists.squid-cache.org/listinfo/squid-dev

Re: [squid-dev] [PATCH] Extend SBufContainerJoin to have prefix and suffix arguments

[Alex Rousskov]

On 11/04/2016 01:12 AM, Kinkie wrote:
> On Thu, Nov 3, 2016 at 10:55 PM, Alex Rousskov
>  wrote:
>> On 11/03/2016 03:19 PM, Kinkie wrote:
>>> On Tue, Nov 1, 2016 at 8:47 PM, Alex Rousskov wrote:
 On 11/01/2016 02:02 PM, Kinkie wrote:
>   the attached patch extends SBufContainerJoin to have prefix and
> suffix arguments.
>>
 I recommend reworking this by adding a dest parameter:
 SBuf (SBuf , ...);

> attached v3 does this.

>  SBuf
> +JoinContainerIntoSBuf(SBuf , ...

Please return dest, not a copy of it. There is no reason to create and
destroy a new SBuf object here IMO. SBuf creation and destruction are
not as expensive as underlying storage copying, but they are still a
measurable expense without justification AFAICT.

There are certainly many cases where using references is a bad idea but
returning a fed-by-reference "dest" is not one of them AFAICT. In fact,
it is nearly the norm in "chainable" calls such as those that append
something.


> +/// variant of JoinContainerIntoSBuf not needing a SBuf lvalue

I recommend a more informative description than retelling of the
function declaration code. For example:

/// convenience JoinContainerIntoSBuf() wrapper with an extra memory
allocation

> +dest.reserveSpace(sz + prefix.length() + suffix.length());

I would reorder the operands to make the code more self-documenting,
especially when using an anonymous variable name like "sz":

  dest.reserveSpace(prefix.length() + sz + suffix.length());


> I am not generally worried as it seems you are about copying SBufs as
> long as the underlying storage is not reallocated needlessly. 

Unfortunately, all three patch versions reallocate storage needlessly
(for various reasons). You can study the attached debugging from the
attached patch to see what is actually going on in various
JoinContainerIntoSBuf implementations. It may surprise and inspire you
to make the code better. It did surprise and inspire me (but I wish I
was not doing this legwork!).


Thank you,

Alex.

2016/11/04 11:47:21.841| test starts
2016/11/04 11:47:21.841| 24,8| SBuf.cc(42) SBuf: SBuf2698 created
2016/11/04 11:47:21.841| 24,8| SBuf.cc(908) cow: SBuf2698 new size:1024
2016/11/04 11:47:21.841| 24,8| SBuf.cc(878) reAlloc: SBuf2698 new size: 1024
2016/11/04 11:47:21.841| 24,9| MemBlob.cc(56) MemBlob: constructed, this=0x202eb70 id=blob1484 reserveSize=1024
2016/11/04 11:47:21.841| 24,8| MemBlob.cc(101) memAlloc: blob1484 memAlloc: requested=1024, received=1024
2016/11/04 11:47:21.841| 24,7| SBuf.cc(887) reAlloc: SBuf2698 new store capacity: 1024
2016/11/04 11:47:21.841| test appended #0: 

2016/11/04 11:47:21.841| 24,7| SBuf.cc(202) append: from c-string to id SBuf2698
2016/11/04 11:47:21.841| 24,7| SBuf.cc(153) rawSpace: reserving 5 for SBuf2698
2016/11/04 11:47:21.841| 24,7| SBuf.cc(160) rawSpace: SBuf2698 not growing
2016/11/04 11:47:21.841| 1,2| AccessLogEntry.cc(32) JoinContainerIntoSBuf1: started
2016/11/04 11:47:21.841| 24,8| SBuf.cc(42) SBuf: SBuf2699 created
2016/11/04 11:47:21.841| 1,2| AccessLogEntry.cc(34) JoinContainerIntoSBuf1: created empty buf
2016/11/04 11:47:21.841| 24,8| SBuf.cc(908) cow: SBuf2699 new size:100
2016/11/04 11:47:21.841| 24,8| SBuf.cc(878) reAlloc: SBuf2699 new size: 100
2016/11/04 11:47:21.841| 24,9| MemBlob.cc(56) MemBlob: constructed, this=0x202e9f0 id=blob1485 reserveSize=100
2016/11/04 11:47:21.841| 24,8| MemBlob.cc(101) memAlloc: blob1485 memAlloc: requested=100, received=128
2016/11/04 11:47:21.841| 24,7| SBuf.cc(887) reAlloc: SBuf2699 new store capacity: 128
2016/11/04 11:47:21.841| 1,2| AccessLogEntry.cc(36) JoinContainerIntoSBuf1: reserved space
2016/11/04 11:47:21.841| 24,7| SBuf.cc(153) rawSpace: reserving 7 for SBuf2699
2016/11/04 11:47:21.841| 24,7| SBuf.cc(160) rawSpace: SBuf2699 not growing
2016/11/04 11:47:21.841| 1,2| AccessLogEntry.cc(38) JoinContainerIntoSBuf1: appended first item
2016/11/04 11:47:21.841| 24,7| SBuf.cc(153) rawSpace: reserving 7 for SBuf2699
2016/11/04 11:47:21.841| 24,7| SBuf.cc(160) rawSpace: SBuf2699 not growing
2016/11/04 11:47:21.841| 1,2| AccessLogEntry.cc(40) JoinContainerIntoSBuf1: appended second item
2016/11/04 11:47:21.841| 24,7| SBuf.cc(153) rawSpace: reserving 14 for SBuf2698
2016/11/04 11:47:21.841| 24,7| SBuf.cc(160) rawSpace: SBuf2698 not growing
2016/11/04 11:47:21.841| 24,8| SBuf.cc(85) ~SBuf: SBuf2699 destructed
2016/11/04 11:47:21.841| 24,9| MemBlob.cc(82) ~MemBlob: destructed, this=0x202e9f0 id=blob1485 capacity=128 size=14
2016/11/04 11:47:21.841| test appended #1: Foo: value1 value1 

2016/11/04 11:47:21.841| 24,7| SBuf.cc(202) append: from c-string to id SBuf2698
2016/11/04 11:47:21.841| 24,7| SBuf.cc(153) rawSpace: reserving 5 for SBuf2698
2016/11/04 11:47:21.841| 24,7| SBuf.cc(160) rawSpace: SBuf2698 not growing
2016/11/04 11:47:21.841| 1,2| AccessLogEntry.cc(47) JoinContainerIntoSBuf2: started
2016/11/04 11:47:21.841| 1,2| AccessLogEntry.cc(48) JoinContainerIntoSBuf2: did not create an 

Re: [squid-dev] [PATCH] Extend SBufContainerJoin to have prefix and suffix arguments

[Kinkie]

On Thu, Nov 3, 2016 at 10:55 PM, Alex Rousskov
 wrote:
> On 11/03/2016 03:19 PM, Kinkie wrote:
>> On Tue, Nov 1, 2016 at 8:47 PM, Alex Rousskov wrote:
>>> On 11/01/2016 02:02 PM, Kinkie wrote:
   the attached patch extends SBufContainerJoin to have prefix and
 suffix arguments.
>
>>> I recommend reworking this by adding a dest parameter:
>>> SBuf (SBuf , ...);
>
>
>> Can simply return the modified SBuf.
>
>>  SBuf
>> -SBufContainerJoin(const Container , const SBuf& separator)
>> +JoinContainerIntoSBuf(SBuf dest, const ContainerIterator ,
>
> This implementation does not avoid copies in a general case: When I
> already have an SBuf with some content, I have to feed my writeable SBuf
> to ContainerToSBuf() to avoid allocating and copying.
>
> AFAICT, the reasonable implementation options are:
>
>   1. Your old simpler implementation without "dest".
>   2. A more efficient implementation with writeable "dest".

attached v3 does this.

> The latest implementation has the complexity of #2 but lacks its
> efficiency. I do not think it is a good API.

I am not generally worried as it seems you are about copying SBufs as
long as the underlying storage is not reallocated needlessly. But it's
very simple to express one call in terms of the other, so I'm doing
just that. I am convinced that the end result of our discussion is
better than what we had started with, and I'm grateful for that.


-- 
Francesco


sbufcontainerjoin-v3.patch
Description: Binary data
___
squid-dev mailing list
squid-dev@lists.squid-cache.org
http://lists.squid-cache.org/listinfo/squid-dev

Re: [squid-dev] [PATCH] Extend SBufContainerJoin to have prefix and suffix arguments

[Alex Rousskov]

On 11/03/2016 03:19 PM, Kinkie wrote:
> On Tue, Nov 1, 2016 at 8:47 PM, Alex Rousskov wrote:
>> On 11/01/2016 02:02 PM, Kinkie wrote:
>>>   the attached patch extends SBufContainerJoin to have prefix and
>>> suffix arguments. 

>> I recommend reworking this by adding a dest parameter:
>> SBuf (SBuf , ...);


> Can simply return the modified SBuf.

>  SBuf
> -SBufContainerJoin(const Container , const SBuf& separator)
> +JoinContainerIntoSBuf(SBuf dest, const ContainerIterator ,

This implementation does not avoid copies in a general case: When I
already have an SBuf with some content, I have to feed my writeable SBuf
to ContainerToSBuf() to avoid allocating and copying.

AFAICT, the reasonable implementation options are:

  1. Your old simpler implementation without "dest".
  2. A more efficient implementation with writeable "dest".

The latest implementation has the complexity of #2 but lacks its
efficiency. I do not think it is a good API.

Alex.

___
squid-dev mailing list
squid-dev@lists.squid-cache.org
http://lists.squid-cache.org/listinfo/squid-dev

Re: [squid-dev] [PATCH] Extend SBufContainerJoin to have prefix and suffix arguments

[Kinkie]

On Tue, Nov 1, 2016 at 8:47 PM, Alex Rousskov
 wrote:
> On 11/01/2016 02:02 PM, Kinkie wrote:
>>   the attached patch extends SBufContainerJoin to have prefix and
>> suffix arguments. This can support a use-case which I found in the
>> current ACLRegexData work I'm following, where we need to transform
>> {"foo", "bar", "gazonk"}
>> into
>> (foo)|(bar)|(gazonk)
>>
>> It can be done with the current version of the SBufContainerJoin
>> function, but it requires one more copy.
>> There are probably further cases of this pattern elsewhere, all hand-rolled.
>
> I agree that the use case is legitimate, but the implementation does not
> solve the underlying cause -- extra copies.

It removes the need of one copy in a common use case, but it can do better.
It also has the drawback of iterating over a full container; reworking
to add a target SBuf and to use begin-end iterators instead of a
container.

> I recommend reworking this by adding a dest parameter:
>
> /// copies all container items (delimited by separator) into dest
> ...
> /// \returns dest
> SBuf (SBuf , ...);
>
> and using that function to implement the SBufContainerJoin() or a
> similarly named convenience wrapper that does not require a dest
> parameter and that returns a copy of an internally used SBuf.

Can simply return the modified SBuf. All the convenience without the
bloat. Also taking the argument by copy; will cow if needed (passing
by reference makes for awkward client code as it'd have to be an
lvalue).
So the common pattern would be:

auto out = JoinContainerIntoSBuf(SBuf(), container.begin(),
container.end(), SBuf("separator"))

> In either case, please do not forget to document that the new prefix and
> suffix are always added, even if the container is empty.

Done.

>>  // sz can be zero in two cases: ... or all items are zero-length.
>
> FWIW, this is a lie. Zero-length items do not result in zero sz unless
> the separator itself is also surprisingly empty. Zero-length items is
> not a special case worth mentioning IMO. The zero-size check should be
> replaced with a direct (begin != end) check to avoid complexity and
> confusion -- it is only needed to avoid dereferencing begin() AFAICT.

Ok.

> HTH,

Sure does :)
Updated patch attached.


-- 
Francesco


sbufcontainerjoin-v2.patch
Description: Binary data
___
squid-dev mailing list
squid-dev@lists.squid-cache.org
http://lists.squid-cache.org/listinfo/squid-dev

Re: [squid-dev] [PATCH] Extend SBufContainerJoin to have prefix and suffix arguments

[Alex Rousskov]

On 11/01/2016 02:02 PM, Kinkie wrote:
>   the attached patch extends SBufContainerJoin to have prefix and
> suffix arguments. This can support a use-case which I found in the
> current ACLRegexData work I'm following, where we need to transform
> {"foo", "bar", "gazonk"}
> into
> (foo)|(bar)|(gazonk)
> 
> It can be done with the current version of the SBufContainerJoin
> function, but it requires one more copy.
> There are probably further cases of this pattern elsewhere, all hand-rolled.

I agree that the use case is legitimate, but the implementation does not
solve the underlying cause -- extra copies.

I recommend reworking this by adding a dest parameter:

/// copies all container items (delimited by separator) into dest
...
/// \returns dest
SBuf (SBuf , ...);

and using that function to implement the SBufContainerJoin() or a
similarly named convenience wrapper that does not require a dest
parameter and that returns a copy of an internally used SBuf.

In either case, please do not forget to document that the new prefix and
suffix are always added, even if the container is empty.


>  // sz can be zero in two cases: ... or all items are zero-length.

FWIW, this is a lie. Zero-length items do not result in zero sz unless
the separator itself is also surprisingly empty. Zero-length items is
not a special case worth mentioning IMO. The zero-size check should be
replaced with a direct (begin != end) check to avoid complexity and
confusion -- it is only needed to avoid dereferencing begin() AFAICT.


HTH,

Alex.

___
squid-dev mailing list
squid-dev@lists.squid-cache.org
http://lists.squid-cache.org/listinfo/squid-dev

[squid-dev] [PATCH] Extend SBufContainerJoin to have prefix and suffix arguments

[Kinkie]

Hi all,
  the attached patch extends SBufContainerJoin to have prefix and
suffix arguments. This can support a use-case which I found in the
current ACLRegexData work I'm following, where we need to transform
{"foo", "bar", "gazonk"}
into
(foo)|(bar)|(gazonk)

It can be done with the current version of the SBufContainerJoin
function, but it requires one more copy.
There are probably further cases of this pattern elsewhere, all hand-rolled.

-- 
Francesco


sbuflist-prefixsuffix-v1.patch
Description: Binary data
___
squid-dev mailing list
squid-dev@lists.squid-cache.org
http://lists.squid-cache.org/listinfo/squid-dev