View mode: basic / threaded / horizontal-split · Log in · Help
June 30, 2012
Re: Creating a Sub-view of a non - RA (hasSlicing) range.
On 6/30/12 11:15 AM, Monarch Dodra wrote:
> On Saturday, 30 June 2012 at 14:22:06 UTC, Andrei Alexandrescu wrote:
>>> 2) The new range is defined as a fixed length from the beginning of the
>>> range, as opposed to start and finish points. If I were to insert new
>>> items into my Slist, the new range would just bump the top items out of
>>> its range.
>>
>> SList's range is not defined by start and finish points. It's defined
>> as the start point, and the finish point is implicit by use of a
>> sentinel (the null pointer).
> Well, what about in the case of a BidirRange from a BDList? Surelly, it
> would be defined by a start and finish point?

Yes. But now you're moving the goalposts because many of your arguments 
referred to SList.

> Take, on the other hand, creates a range, which is defined by a start
> point, and a fixed length. Inserting elements into the middle of the
> original list would bump elements out of the "take range", which remains
> fixed sized.

Correct. take() and takeExactly() work under the assumption there's no 
surreptitious change in the structure of the range underneath. I think 
that's a reasonable decision.

> On the other hand, had I manually shrunk my BDlistRange until it was 5
> elements long, and then inserted elements into the midle of the list, it
> would cause my BDListRange to grow, and nothing to drop out of it.

Right. Generally ranges are not responsible for accurately tracking 
underlying structural changes. There will always be ways to mess up 
things in ways that leave extant ranges unsynchronized.

>> Not sure I understand this, but when we get into the realm of bidir
>> ranges, things get a fair amount better. How would TakeLast work?
>
> Well, if we forget Slist, and just focus on a standard
> BidirectionalRange, say comming from a DList. Things don't really get
> any better, because take still returns just a ForwardRange.

Which is as it should be. How would you otherwise take the first n 
elements of a given doubly-linked list in constant time?

> There is no way of doing, say:
>
> BidirectionalRange aBD = ...;
>
> //Create subrange...
> //aBD = take(aBD, 5); //Error, wrong type
> auto subrange = take(aBD, 5);
>
> if(subrange.back == 5) //Error, subrange does not have a back method.
> //...But that's strange, because aBD IS a bidiretinal range
>
> Since the Take Range it is defined by a begining point and a length,
> there is no way it could give Bidir access.

It's all about what it takes to reach a certain point. You are sensing 
something indeed, but take() is not it. The problem is there's no simple 
way to count 5 starting from the left side of a doubly-linked list, stop 
there, and then create a range from the beginning of the list and that 
mid point. In C++, that's trivial because range ends are separate.

> ----
> I came to D after reading your talk on ranges, and I really liked (and
> am still enjoying) the concept. However, with C++, when you iterate over
> [First, Last), you are also creating a two new ranges: [First, Current)
> & [Current, Last). D doesn't provide that, it only provides a way to
> shrink the current range and create [Current, Last).

Yes, that's a good way of putting it.

> Using range, you don't get [First, Current). At best, you only get
> a)A forward range only
> b)A fixed size range
> c)A range of another type

We could extend the range interface for specific ranges to allow for 
such. However, there hasn't been a strong need so far.


Andrei
July 01, 2012
Re: Creating a Sub-view of a non - RA (hasSlicing) range.
On 30-Jun-12 18:25, Andrei Alexandrescu wrote:
> On 6/30/12 9:15 AM, Dmitry Olshansky wrote:
>> On 30-Jun-12 15:35, Tobias Pankrath wrote:
>>>> Say I have a forward range (for example, an SList[]). I would like to
>>>> create a new range containing only the first 5 elements of that old
>>>> range. How can I do that?
>>>>
>>>
>>> std.algorithm.take.
>>>
>>> But I would generally avoid SList.
>>
>> Indeed. I'd be hard pressed to devise realistic use case where it
>> performs better.
>
> Singly-linked lists are frequently used with lock-free algorithms.

As post involved terms like "generally" I pointed out that indeed List 
should not be used "generally" :) Their value in certain scenarios is 
remarkable, or rather of linked storage such as in free lists, and (like 
you mentioned) certain lock-free algorithms.

Let's not forget however that what people seek is lock-free queues and 
other high-level abstractions. S-lists just happen to be a means to an 
end that works on current hardware.

I totally expect a new wave of simpler lock-free algorithms with things 
like Intel's TSX and something analogous that AMD will have.
(others would either copy or redesign similar things as it's an obvious 
need for the future multicores)

There a lot of links but this gives a nice overview and is fairly new:
http://arstechnica.com/business/2012/02/transactional-memory-going-mainstream-with-intel-haswell/
> Generally it's simplistic to compare slists with arrays as to "which
> performs better" because they have different primitives.

Agreed. Though it's not at all uncommon to mix things up in awful ways. 
*cough* Java *cough*


-- 
Dmitry Olshansky
July 01, 2012
Re: Creating a Sub-view of a non - RA (hasSlicing) range.
On Saturday, 30 June 2012 at 23:51:42 UTC, Andrei Alexandrescu 
wrote:
> Yes. But now you're moving the goalposts because many of your 
> arguments referred to SList.
I'm sorry, that's not what I meant to do. The goal post was not 
moved, rather misplaced to begin with. Using SList for making my 
point was not the best choice of containers. I'd hae used a 
"DList" like container if I had one.


On Saturday, 30 June 2012 at 23:51:42 UTC, Andrei Alexandrescu 
wrote:
> Correct. take() and takeExactly() work under the assumption 
> there's no surreptitious change in the structure of the range 
> underneath. I think that's a reasonable decision.
Most of the time yes. But for certain "partitioning" algorithms, 
those that _cut_ a range into several subranges (for example 
"findSplit"), such "surreptitious" change should (IMO) be 
expected and supported.


On Saturday, 30 June 2012 at 23:51:42 UTC, Andrei Alexandrescu 
wrote:
> Which is as it should be. How would you otherwise take the 
> first n elements of a given doubly-linked list in constant time?
Constanst time, I don't know. I'm still looking for a way to do 
it in o(N) ;)


On Saturday, 30 June 2012 at 23:51:42 UTC, Andrei Alexandrescu 
wrote:
> It's all about what it takes to reach a certain point. You are 
> sensing something indeed, but take() is not it. The problem is 
> there's no simple way to count 5 starting from the left side of 
> a doubly-linked list, stop there, and then create a range from 
> the beginning of the list and that mid point. In C++, that's 
> trivial because range ends are separate.
>
>> ----
>> I came to D after reading your talk on ranges, and I really 
>> liked (and
>> am still enjoying) the concept. However, with C++, when you 
>> iterate over
>> [First, Last), you are also creating a two new ranges: [First, 
>> Current)
>> & [Current, Last). D doesn't provide that, it only provides a 
>> way to
>> shrink the current range and create [Current, Last).
>
> Yes, that's a good way of putting it.
>
>> Using range, you don't get [First, Current). At best, you only 
>> get
>> a)A forward range only
>> b)A fixed size range
>> c)A range of another type
>
> We could extend the range interface for specific ranges to 
> allow for such. However, there hasn't been a strong need so far.
>
>
> Andrei

Thanks again for your replies. I'm really enjoying using D and 
ranges, and I get that nothing is "free", and this issue is one 
of the by products of moving from iterators-pairs to more 
powerful, but restrictive, ranges.

I get the "no sense in making things more complicated if there is 
not a strong need", but at the same time, I've always felt that a 
language's algorithm facility should always we imaculate. Further 
more, it really feels as if the interface is just one concept shy 
of being able to make something like this work...

Something like...
"inverseRangeBegin(R big, R small)": Creates a range that begins 
where big starts, and ends where small starts. R must be at least 
bidirectional. small must be included inside big.

From an implementation point of view, I think any container, and 
even arrays, can do it. I pretty sure this is compeltly feasable. 
Just off the top of my head. I'm sure there are brighter thinkers 
out there that have put more thought into it.
July 01, 2012
Re: Creating a Sub-view of a non - RA (hasSlicing) range.
On Sunday, 1 July 2012 at 13:22:17 UTC, monarch_dodra wrote:
> Something like...
> "inverseRangeBegin(R big, R small)": Creates a range that 
> begins where big starts, and ends where small starts. R must be 
> at least bidirectional. small must be included inside big.
>
> From an implementation point of view, I think any container, 
> and even arrays, can do it. I pretty sure this is compeltly 
> feasable. Just off the top of my head. I'm sure there are 
> brighter thinkers out there that have put more thought into it.

Or not. On second thought, while I'm sure there might be an 
implementable solution, I doubt it could be done with any real 
safety guarantees.
July 02, 2012
Re: Creating a Sub-view of a non - RA (hasSlicing) range.
Have you had a look at dcollection ?

http://www.dsource.org/projects/dcollections

There is a doubly linked list implementation, with range and cursors 
(entities that have iterator functionalities).
July 03, 2012
Re: Creating a Sub-view of a non - RA (hasSlicing) range.
On Sat, Jun 30, 2012 at 6:27 AM, bearophile <bearophileHUGS@lycos.com>wrote:

> Tobias Pankrath:
>
>
>  But I would generally avoid SList.
>>
>
> It's not good.
>
> And in general linked lists are quite overrated. On modern CPUs it's not
> easy to find situations where a linked list is better than a dynamic array
> or a chunked array (that is a dynamic array of pointers to arrays. It's
> often used to implement deques, etc).
>
>
> Regarding arrays, maybe a StableVector will be good to have in Phobos:
> http://www.boost.org/doc/libs/**1_50_0_beta1/doc/html/**
> container/non_standard_**containers.html#container.non_**
> standard_containers.stable_**vector<http://www.boost.org/doc/libs/1_50_0_beta1/doc/html/container/non_standard_containers.html#container.non_standard_containers.stable_vector>
>
> Bye,
> bearophile
>

I also think flat_map/_set from that same boost library would be great
additions when the time comes to add new stuff to std.container.  Red black
trees are kind of a niche container[1].  I replaced almost all of my usage
of C++'s std::set and std::map with flat_map and flat_set and saw better
memory use and far fewer cache misses (assuming I was reading the profiler
correctly).  It was win-win since I rarely needed std::set/::map's
exclusive features (iterator stability, log N insertions).  I believe I've
read Andrei added something just like these to Loki.


[1] http://lafstern.org/matt/col1.pdf : Why you shouldn't use set (and what
you should use instead)

Regards,
Brad Anderson
Next ›   Last »
1 2
Top | Discussion index | About this forum | D home