Menu
Search

Forums

Forum Index

September 01, 2021
Gravatar of Per NordlöwPosted by Per Nordlöw
in reply to deadalnix		Reply
Per Nordlöw
Gravatar of Per Nordlöw
Posted in reply to deadalnix


Reply

On Wednesday, 1 September 2021 at 10:33:47 UTC, deadalnix wrote:

>

I started looking into this after a short discussion with Andrei :)

Also highly related is Atila's work on doing std.typecons.RefCounted safe at https://github.com/dlang/phobos/pull/8101. Seems stalled, though.

September 01, 2021
Gravatar of deadalnixPosted by deadalnix
in reply to Per Nordlöw		Reply
deadalnix
Gravatar of deadalnix
Posted in reply to Per Nordlöw


Reply

On Wednesday, 1 September 2021 at 20:48:10 UTC, Per Nordlöw wrote:

>

On Wednesday, 1 September 2021 at 00:52:04 UTC, deadalnix wrote:

>

You seem to be confused. The C++11 standard prohibits std::string from using COW. Existing C++ implementations were using COW, and getting out of it was what was a disaster (notably, there were breaking ABI changes, which the C++ ecosystem is not well suited to handle).

In what ways was it a disaster? Because most strings are small enough to benefit from the small string optimization?

It was a disaster because gcc's standard lib used a COW string implementation, but had to change it when moving the C++11. Considering virutally everything uses string and that a lot of C++ software is distributed in binary format, and that the standard lib is often liked in live at launch time by the OS, you are faced with an ABI breakage nightmare.

September 01, 2021
Gravatar of Per NordlöwPosted by Per Nordlöw
in reply to rikki cattermole		Reply
Per Nordlöw
Gravatar of Per Nordlöw
Posted in reply to rikki cattermole


Reply

On Wednesday, 1 September 2021 at 12:09:19 UTC, rikki cattermole wrote:

>

Unrolled linked list, a linked list with X number of entries per node.

Yes, where each node typically is sized to fit in a single cache-line. Suitable for small element types.

I don't know why an UnrolledList is preferred over a traditional vector type bundled with an allocator that does the same grouping of allocations, though.

September 02, 2021
Gravatar of rikki cattermolePosted by rikki cattermole
in reply to Per Nordlöw		Reply
rikki cattermole
Gravatar of rikki cattermole
Posted in reply to Per Nordlöw


Reply
On 02/09/2021 8:55 AM, Per Nordlöw wrote:
> On Wednesday, 1 September 2021 at 12:09:19 UTC, rikki cattermole wrote:
>> Unrolled linked list, a linked list with X number of entries per node.
> 
> Yes, where each node typically is sized to fit in a single cache-line. Suitable for small element types.
> 
> I don't know why an UnrolledList is preferred over a traditional vector type bundled with an allocator that does the same grouping of allocations, though.

All depends on how the vector is implemented. If its just an array that is resized as required with extra capacity, then obviously there is memory fragmentation issues that can result in allocation failing.

But I think each have different memory patterns associated with it, so it may not be clear cut.

For example I'm working on a color palette data structure using an unrolled linked list as the basis.

Insertions, removals are both quite common here, but so is only appending. And of course quite importantly you want fairly fast skipping of entries (hence unrolled rather than a straight linked list) to find the one you want.
September 02, 2021
Gravatar of ikodPosted by ikod
in reply to deadalnix		Reply
ikod
Gravatar of ikod
Posted in reply to deadalnix


Reply

On Tuesday, 31 August 2021 at 17:21:02 UTC, deadalnix wrote:

>

I want to start working on a container library. Interestingly enough, I don't think we have what we need on that front.

 >

Now onto the design:

  • Value types. It is very easy to turn a value into a reference type, not so much the other way around. reference type also come with a bag of edges cases, like the collection being null vs empty, that cause confusion and problems in practice.

My collections library[1] @safety inherited from the stored data types. Any data access methods that returns reference marked with '@system', so you can't use it easily in @safe code.

>

I have a good idea how to solve all these problems. I have no idea how to solve the type qualifier one. I need help.

You didn't mention iterator stability.

[1] https://github.com/ikod/ikod-containers

September 02, 2021
Gravatar of KagaminPosted by Kagamin
in reply to Steven Schveighoffer		Reply
Kagamin
Gravatar of Kagamin
Posted in reply to Steven Schveighoffer


Reply

On Wednesday, 1 September 2021 at 12:32:36 UTC, Steven Schveighoffer wrote:

>

To further explain for readers, the issue is:

void foo(T)(Vector!(const(T)) arg);

This compiles:

struct Vector(T){}
void f(T:const(U),U)(Vector!T arg);
void f1()
{
    Vector!(const int) a;
    f(a);
}
September 02, 2021
Gravatar of KagaminPosted by Kagamin
in reply to deadalnix		Reply
Kagamin
Gravatar of Kagamin
Posted in reply to deadalnix


Reply

On Tuesday, 31 August 2021 at 17:21:02 UTC, deadalnix wrote:

>
  • Not expose much of its internals.

Do you want to expose the COW detail in the interface?

September 02, 2021
Gravatar of deadalnixPosted by deadalnix
in reply to Kagamin		Reply
deadalnix
Gravatar of deadalnix
Posted in reply to Kagamin


Reply

On Thursday, 2 September 2021 at 09:15:10 UTC, Kagamin wrote:

>

On Tuesday, 31 August 2021 at 17:21:02 UTC, deadalnix wrote:

>
  • Not expose much of its internals.

Do you want to expose the COW detail in the interface?

It doesn't need to be explicit, but in many instances, this is going to be visible, for instance, if the type stored has a copy constructor, then copying the container will be a very visible operation.

« First   ‹ Prev
1 2 3 4 5
Next ›   Last »