Discussion:
Escaping the Tyranny of the GC: std.rcstring, first blood
(too old to reply)
Andrei Alexandrescu via Digitalmars-d
2014-09-15 02:26:58 UTC
Permalink
Walter, Brad, myself, and a couple of others have had a couple of quite
exciting ideas regarding code that is configurable to use the GC or
alternate resource management strategies. One thing that became obvious
to us is we need to have a reference counted string in the standard
library. That would be usable with applications that want to benefit
from comfortable string manipulation whilst using classic reference
counting for memory management. I'll get into more details into the
mechanisms that would allow the stdlib to provide functionality for both
GC strings and RC strings; for now let's say that we hope and aim for
swapping between these with ease. We hope that at one point people would
be able to change one line of code, rebuild, and get either GC or RC
automatically (for Phobos and their own code).

The road there is long, but it starts with the proverbial first step. As
it were, I have a rough draft of a almost-drop-in replacement of string
(aka immutable(char)[]). Destroy with maximum prejudice:

http://dpaste.dzfl.pl/817283c163f5

For now RCString supports only immutable char as element type. That
means you can't modify individual characters in an RCString object but
you can take slices, append to it, etc. - just as you can with string. A
compact reference counting scheme is complemented with a small buffer
optimization, so performance should be fairly decent.

Somewhat surprisingly, pure constructors and inout took good care of
qualified semantics (you can convert a mutable to an immutable string
and back safely). I'm not sure whether semantics there are a bit too
lax, but at least for RCString they turned out to work beautifully and
without too much fuss.

The one wrinkle is that you need to wrap string literals "abc" with
explicit constructor calls, e.g. RCString("abc"). This puts RCString on
a lower footing than built-in strings and makes swapping configurations
a tad more difficult.

Currently I've customized RCString with the allocation policy, which I
hurriedly reduced to just one function with the semantics of realloc.
That will probably change in a future pass; the point for now is that
allocation is somewhat modularized away from the string workings.

So, please fire away. I'd appreciate it if you used RCString in lieu of
string and note the differences. The closer we get to parity in
semantics, the better.


Thanks,

Andrei
Vladimir Panteleev via Digitalmars-d
2014-09-15 02:52:35 UTC
Permalink
On Monday, 15 September 2014 at 02:26:19 UTC, Andrei Alexandrescu
Post by Andrei Alexandrescu via Digitalmars-d
The road there is long, but it starts with the proverbial first
step.
An unrelated question, but how will reference counting work with
classes?

I've recently switched my networking library's raw memory wrapper
to reference counting (previously it just relied on the GC for
cleanup), and it was going well until I've hit a brick wall.

The thing with reference counting is it doesn't seem to make
sense to do it half-way. Everything across the ownership chain
must be reference counted, because otherwise the non-ref-counted
link will hold on to its ref-counted child objects forever (until
the next GC cycle).

In my case, the classes in my applications were holding on to my
reference-counted structs, and wouldn't let go until they were
eventually garbage-collected. I can't convert the classes to
structs because I need their inheritance/polymorphism, and I
don't see an obvious way to refcount classes (RefCounted
explicitly does not support classes).

Am I overlooking something?
Andrei Alexandrescu via Digitalmars-d
2014-09-15 03:53:13 UTC
Permalink
Post by Andrei Alexandrescu via Digitalmars-d
The road there is long, but it starts with the proverbial first step.
An unrelated question, but how will reference counting work with classes?
I've recently switched my networking library's raw memory wrapper to
reference counting (previously it just relied on the GC for cleanup),
and it was going well until I've hit a brick wall.
The thing with reference counting is it doesn't seem to make sense to do
it half-way. Everything across the ownership chain must be reference
counted, because otherwise the non-ref-counted link will hold on to its
ref-counted child objects forever (until the next GC cycle).
In my case, the classes in my applications were holding on to my
reference-counted structs, and wouldn't let go until they were
eventually garbage-collected. I can't convert the classes to structs
because I need their inheritance/polymorphism, and I don't see an
obvious way to refcount classes (RefCounted explicitly does not support
classes).
Am I overlooking something?
At least for the time being, bona fide class objects with refcounted
members will hold on to them until they're manually freed or a GC cycle
comes about.

We're thinking of a number of schemes for reference counted objects, and
we think a bottom-up approach to design would work well here: try a
simple design and assess its limitations. In this case, it would be
great if you tried to use RefCounted with your class objects and figure
out what its limitations are.


Thanks,

Andrei
Vladimir Panteleev via Digitalmars-d
2014-09-15 18:30:26 UTC
Permalink
On Monday, 15 September 2014 at 03:52:34 UTC, Andrei Alexandrescu
Post by Andrei Alexandrescu via Digitalmars-d
We're thinking of a number of schemes for reference counted
objects, and we think a bottom-up approach to design would work
well here: try a simple design and assess its limitations. In
this case, it would be great if you tried to use RefCounted
with your class objects and figure out what its limitations are.
RefCounted currently does not work at all with class objects.
This is explicitly indicated in RefCounted's template constraint.

Are you saying we should try to make RefCounted work with classes
or something else?
Andrei Alexandrescu via Digitalmars-d
2014-09-15 18:44:05 UTC
Permalink
Post by Andrei Alexandrescu via Digitalmars-d
We're thinking of a number of schemes for reference counted objects,
and we think a bottom-up approach to design would work well here: try
a simple design and assess its limitations. In this case, it would be
great if you tried to use RefCounted with your class objects and
figure out what its limitations are.
RefCounted currently does not work at all with class objects. This is
explicitly indicated in RefCounted's template constraint.
Are you saying we should try to make RefCounted work with classes or
something else?
Yes, we should define RefCounted for classes as well. (Sorry, I was
confused.) Extending to class types should be immediate at least in the
first approximation. Then we can stand back and take a look at the
advantages and liabilities.

Could someone please initiate that work?


Thanks,

Andrei
deadalnix via Digitalmars-d
2014-09-15 04:50:21 UTC
Permalink
I don't want to be the smart ass that did nothing and complains
about what other did, but I'll be it anyway.

It doesn't look very scalable to me to implement various versions
of modules with various memory management schemes. Inevitably,
these will have different subtle variation in semantic, different
set of bugs, it is twice as many work to maintain and so on.

Have you tried to explore solution where an allocator is passed
to functions (as far as I can tell, this wasn't very successful
in C++, but D greater metaprogramming capabilities may offer
better solutions than C++'s) ?

Another option is to use output ranges. This look like an area
that is way underused in D. It looks like it is possible for the
allocation policy to be part of the output range, and so we can
let users decide without duplication bunch of code.

Finally, concepts like isolated allow the compiler to insert free
in the generated code in a safe manner. In the same way, it is
possible to remove a bunch of GC allocation by sticking some
passes in the middle of the optimizer (
Andrei Alexandrescu via Digitalmars-d
2014-09-15 05:47:06 UTC
Permalink
I don't want to be the smart ass that did nothing and complains about
what other did, but I'll be it anyway.
It doesn't look very scalable to me to implement various versions of
modules with various memory management schemes. Inevitably, these will
have different subtle variation in semantic, different set of bugs, it
is twice as many work to maintain and so on.
I've got to give it to you - it's rare to get a review on a design that
hasn't been described yet :o).

There is no code duplication.
Have you tried to explore solution where an allocator is passed to
functions (as far as I can tell, this wasn't very successful in C++, but
D greater metaprogramming capabilities may offer better solutions than
C++'s) ?
Another option is to use output ranges. This look like an area that is
way underused in D. It looks like it is possible for the allocation
policy to be part of the output range, and so we can let users decide
without duplication bunch of code.
I've been thinking for a long time about these:

1. Output ranges;

2. Allocator objects;

3. Reference counting and encapsulations thereof.

Each has a certain attractiveness, particularly when thought of in the
context of stdlib which tends to use limited, confined allocation patterns.

Took me a while to figure there's some red herring tracking there. I
probably half convinced Walter too.

The issue is these techniques seem they overlap at all, but in fact the
overlap is rather thin. In fact, output ranges are rather limited: they
only fit the bill when (a) only output needs to be allocated, and (b)
output is produced linearly. Outside these applications, there's simply
no use.

As soon as thought enters more complex applications, the lure of
allocators becomes audible. Pass an allocator into the algorithm, they
say, and you've successfully pushed up memory allocation policy from the
algorithm into the client.

The reality is allocators are low-level, unstructured devices that
allocate memory but are not apt at managing it beyond blindly responding
to client calls "allocate this much memory, now take it back". The many
subtleties associated with actual _management_ of memory via reference
counting (evidence: http://dpaste.dzfl.pl/817283c163f5) are completely
lost on allocators.

I am convinced that we need to improve the lot of people who want to use
the stdlib without a garbage collector, or with minimal use of it (more
on that later). To do so, it is obvious we need good alternative
abstractions, and reference counting is an obvious contender.
Finally, concepts like isolated allow the compiler to insert free in the
generated code in a safe manner. In the same way, it is possible to
remove a bunch of GC allocation by sticking some passes in the middle of
the optimizer (
)


Andrei
Rikki Cattermole via Digitalmars-d
2014-09-15 04:51:35 UTC
Permalink
Post by Andrei Alexandrescu via Digitalmars-d
The one wrinkle is that you need to wrap string literals "abc"
with explicit constructor calls, e.g. RCString("abc"). This
puts RCString on a lower footing than built-in strings and
makes swapping configurations a tad more difficult.
A few ideas:

import std.traits : isSomeString;
auto refCounted(T)(T value) if (isSomeString!T) {
static if (is(T == string))
return new RCXString!(immutable char)(value);
//....
static assert(0);
}

static assert("abc".refCounted == "abc");

Wrapper type scenario. May look nicer.

Other which would require a language change of:

struct MyType {
string value;
alias value this;

this(string value) {
this.value = value;
}
}

static assert("abc".MyType == "abc");

*shudder* does remind me a little too much of the Jade
programming language with its casts like that.

There is one other thing which I don't think people are taking
too seriously is my idea of using with statement to swap out e.g.
the GC during runtime.

with(myAllocator) {
Foo foo = new Foo; // calls the allocator to assign memory for
new instance of Foo
}
// tell allocator to free foo

with(myAllocator) {
Foo foo = new Foo; // calls the allocator to assign memory for
new instance of Foo
myFunc(foo);
}
// if myFunc modifies foo or if myFunc passes foo to another
function then:
// tell GC it has to free it when able to
// otherwise:
// tell allocator to free foo

class MyAllocator : Allocator {
void opWithIn(string file = __MODULE__, int line = __LINE__,
string function = ?) {
GC.pushAllocator(this);
}

void opWithOut(string file = __MODULE__, int line = __LINE__,
string function = ?) {
GC.popAllocator();
}
}

By using the with statement this is possible:
void something() {
with(new RCAllocator) {
string value = "Hello World!"; // allocates memory via
RCAllocator
} // frees here
}
Andrei Alexandrescu via Digitalmars-d
2014-09-15 05:51:15 UTC
Permalink
Post by Rikki Cattermole via Digitalmars-d
static assert("abc".refCounted == "abc");
The idea is we want to write things like:

String s = "abc";

and have it be either refcounted or "classic" depending on the
definition of String. With a user-defined String, you need:

String s = String("abc");

or

auto s = String("abc");


Andrei
Jakob Ovrum via Digitalmars-d
2014-09-15 05:55:32 UTC
Permalink
On Monday, 15 September 2014 at 05:50:36 UTC, Andrei Alexandrescu
Post by Andrei Alexandrescu via Digitalmars-d
and have it be either refcounted or "classic" depending on the
String s = String("abc");
The following works fine:

RCString s = "abc";

It will call RCString.this with "abc". The problem is passing
string literals or slices to functions that receive RCString.
Andrei Alexandrescu via Digitalmars-d
2014-09-15 07:22:50 UTC
Permalink
Post by Jakob Ovrum via Digitalmars-d
Post by Andrei Alexandrescu via Digitalmars-d
and have it be either refcounted or "classic" depending on the
String s = String("abc");
RCString s = "abc";
It will call RCString.this with "abc". The problem is passing string
literals or slices to functions that receive RCString.
Yah, sorry for the confusion. -- Andrei
Rikki Cattermole via Digitalmars-d
2014-09-15 06:18:32 UTC
Permalink
Post by Andrei Alexandrescu via Digitalmars-d
Post by Rikki Cattermole via Digitalmars-d
static assert("abc".refCounted == "abc");
String s = "abc";
and have it be either refcounted or "classic" depending on the
String s = String("abc");
or
auto s = String("abc");
Andrei
Yeah I thought so.
Still I think the whole with statement would be a better direction to
go, but what ever. I'll drop it.
Jakob Ovrum via Digitalmars-d
2014-09-15 07:41:23 UTC
Permalink
On Monday, 15 September 2014 at 02:26:19 UTC, Andrei Alexandrescu
Post by Andrei Alexandrescu via Digitalmars-d
So, please fire away. I'd appreciate it if you used RCString in
lieu of string and note the differences. The closer we get to
parity in semantics, the better.
It should support appending single code units:

---
alias String = RCString;

void main()
{
String s = "abc";

s ~= cast(char)'0';
s ~= cast(wchar)'0';
s ~= cast(dchar)'0';

writeln(s); // abc000
}
---

Works with C[], fails with RCString. The same is true for
concatenation.
John Colvin via Digitalmars-d
2014-09-15 08:51:54 UTC
Permalink
On Monday, 15 September 2014 at 02:26:19 UTC, Andrei Alexandrescu
Post by Andrei Alexandrescu via Digitalmars-d
Walter, Brad, myself, and a couple of others have had a couple
of quite exciting ideas regarding code that is configurable to
use the GC or alternate resource management strategies. One
thing that became obvious to us is we need to have a reference
counted string in the standard library. That would be usable
with applications that want to benefit from comfortable string
manipulation whilst using classic reference counting for memory
management. I'll get into more details into the mechanisms that
would allow the stdlib to provide functionality for both GC
strings and RC strings; for now let's say that we hope and aim
for swapping between these with ease. We hope that at one point
people would be able to change one line of code, rebuild, and
get either GC or RC automatically (for Phobos and their own
code).
The road there is long, but it starts with the proverbial first
step. As it were, I have a rough draft of a almost-drop-in
replacement of string (aka immutable(char)[]). Destroy with
http://dpaste.dzfl.pl/817283c163f5
For now RCString supports only immutable char as element type.
That means you can't modify individual characters in an
RCString object but you can take slices, append to it, etc. -
just as you can with string. A compact reference counting
scheme is complemented with a small buffer optimization, so
performance should be fairly decent.
Somewhat surprisingly, pure constructors and inout took good
care of qualified semantics (you can convert a mutable to an
immutable string and back safely). I'm not sure whether
semantics there are a bit too lax, but at least for RCString
they turned out to work beautifully and without too much fuss.
The one wrinkle is that you need to wrap string literals "abc"
with explicit constructor calls, e.g. RCString("abc"). This
puts RCString on a lower footing than built-in strings and
makes swapping configurations a tad more difficult.
Currently I've customized RCString with the allocation policy,
which I hurriedly reduced to just one function with the
semantics of realloc. That will probably change in a future
pass; the point for now is that allocation is somewhat
modularized away from the string workings.
So, please fire away. I'd appreciate it if you used RCString in
lieu of string and note the differences. The closer we get to
parity in semantics, the better.
Thanks,
Andrei
Why not open this up to all slices of immutable value type
elements?
Andrei Alexandrescu via Digitalmars-d
2014-09-15 14:40:04 UTC
Permalink
Why not open this up to all slices of immutable value type elements?
That will come in good time. For now I didn't want to worry about
indirections, constructors, etc. -- Andrei
monarch_dodra via Digitalmars-d
2014-09-15 09:50:28 UTC
Permalink
On Monday, 15 September 2014 at 02:26:19 UTC, Andrei Alexandrescu
Post by Andrei Alexandrescu via Digitalmars-d
So, please fire away. I'd appreciate it if you used RCString in
lieu of string and note the differences. The closer we get to
parity in semantics, the better.
Thanks,
Andrei
***Blocker thoughts***
(unless I'm misunderstood)

- Does not provide Forward range iteration that I can find. This
makes it unuseable for algorithms:
find (myRCString, "hello"); //Nope
Also, adding "save" to make it forward might not be a good idea,
since it would also mean it becomes an RA range (which it isn't).

- Does not provide any way to (even "unsafely") extract a raw
array. Makes it difficult to interface with existing functions.
It would also be important for "RCString aware" functions to be
properly optimized (eg memchr for searching etc...)

- No way to "GC-dup" the RCString. giving "dup"/"idup" members on
RCstring, for when you really just need to revert to pure
un-collected GC.

Did I miss something? It seems actually *doing* something with an
RCString is really difficult.


***Random implementation thought:***
"size_t maxSmall = 23" is (IMO) gratuitous: It can only lead to
non-optimization and binary bloat. We'd end up having
incompatible RCStrings, which is bad.

At the very least, I'd say make it a parameter *after* the
"realloc" function (as arguably, maxSmall depends on the
allocation scheme, and not the other way around).

In particular, it seems RCBuffer does not depend on maxSmall, so
it might be possible to move that out of RCXString.

***Extra thoughts***
There have been requests for non auto-decoding strings. Maybe
this would be a good opportunity for "RCXUString" ?
via Digitalmars-d
2014-09-15 13:15:27 UTC
Permalink
Post by Vladimir Panteleev via Digitalmars-d
On Monday, 15 September 2014 at 02:26:19 UTC, Andrei
Post by Andrei Alexandrescu via Digitalmars-d
So, please fire away. I'd appreciate it if you used RCString
in lieu of string and note the differences. The closer we get
to parity in semantics, the better.
Thanks,
Andrei
***Blocker thoughts***
(unless I'm misunderstood)
- Does not provide Forward range iteration that I can find.
find (myRCString, "hello"); //Nope
Also, adding "save" to make it forward might not be a good
idea, since it would also mean it becomes an RA range (which it
isn't).
No, RA is not implied by forward.
Post by Vladimir Panteleev via Digitalmars-d
- Does not provide any way to (even "unsafely") extract a raw
array. Makes it difficult to interface with existing functions.
It would also be important for "RCString aware" functions to be
properly optimized (eg memchr for searching etc...)
Another perfect use case for borrowing...
Post by Vladimir Panteleev via Digitalmars-d
***Extra thoughts***
There have been requests for non auto-decoding strings. Maybe
this would be a good opportunity for "RCXUString" ?
Yes. I'm surprised by this proposal, because I thought Walter was
totally opposed to a dedicated string type. If it now becomes
acceptable, it's a good opportunity for moving away for
auto-decoding.
monarch_dodra via Digitalmars-d
2014-09-15 13:38:56 UTC
Permalink
Post by via Digitalmars-d
Post by monarch_dodra via Digitalmars-d
- Does not provide Forward range iteration that I can find.
find (myRCString, "hello"); //Nope
Also, adding "save" to make it forward might not be a good
idea, since it would also mean it becomes an RA range (which
it isn't).
No, RA is not implied by forward.
Right, but RCString already has the RA primitives (and
hasLength), it's only missing ForwardRange traits to *also*
become RandomAccess.
Andrei Alexandrescu via Digitalmars-d
2014-09-15 14:45:34 UTC
Permalink
- Does not provide Forward range iteration that I can find. This makes
find (myRCString, "hello"); //Nope
Also, adding "save" to make it forward might not be a good idea, since
it would also mean it becomes an RA range (which it isn't).
If we move forward with this type, traits will recognize it as isSomeString.
- Does not provide any way to (even "unsafely") extract a raw array.
Makes it difficult to interface with existing functions. It would also
be important for "RCString aware" functions to be properly optimized (eg
memchr for searching etc...)
- No way to "GC-dup" the RCString. giving "dup"/"idup" members on
RCstring, for when you really just need to revert to pure un-collected GC.
Nice. But then I'm thinking, wouldn't people think .dup produces another
RCString?
Did I miss something? It seems actually *doing* something with an
RCString is really difficult.
Yah it's too tightly wound right now, but that's the right way!
***Random implementation thought:***
"size_t maxSmall = 23" is (IMO) gratuitous: It can only lead to
non-optimization and binary bloat. We'd end up having incompatible
RCStrings, which is bad.
At the very least, I'd say make it a parameter *after* the "realloc"
function (as arguably, maxSmall depends on the allocation scheme, and
not the other way around).
I think realloc will disappear.
In particular, it seems RCBuffer does not depend on maxSmall, so it
might be possible to move that out of RCXString.
***Extra thoughts***
There have been requests for non auto-decoding strings. Maybe this would
be a good opportunity for "RCXUString" ?
For now I was aiming at copying string's semantics.


Andrei
Kagamin via Digitalmars-d
2014-09-15 15:11:47 UTC
Permalink
On Monday, 15 September 2014 at 14:44:53 UTC, Andrei Alexandrescu
Post by Andrei Alexandrescu via Digitalmars-d
For now I was aiming at copying string's semantics.
Then range primitives should move to std.range or where they are
now. By default string iterates over its array elements, which is
char in this case.
Wyatt via Digitalmars-d
2014-09-15 16:45:22 UTC
Permalink
On Monday, 15 September 2014 at 14:44:53 UTC, Andrei Alexandrescu
Post by Andrei Alexandrescu via Digitalmars-d
Post by monarch_dodra via Digitalmars-d
- No way to "GC-dup" the RCString. giving "dup"/"idup" members
on RCstring, for when you really just need to revert to pure
un-collected GC.
Nice. But then I'm thinking, wouldn't people think .dup
produces another RCString?
I certainly would. If I wanted a GC string from an RCString, I'd
probably reach for std.conv for clarity's sake. e.g.

RCString foo = "banana!";
string bar = to!string(foo);

-Wyatt
Jacob Carlborg via Digitalmars-d
2014-09-15 19:54:19 UTC
Permalink
Post by Andrei Alexandrescu via Digitalmars-d
- Does not provide Forward range iteration that I can find. This makes
find (myRCString, "hello"); //Nope
Also, adding "save" to make it forward might not be a good idea, since
it would also mean it becomes an RA range (which it isn't).
If we move forward with this type, traits will recognize it as
isSomeString.
- Does not provide any way to (even "unsafely") extract a raw array.
Makes it difficult to interface with existing functions. It would also
be important for "RCString aware" functions to be properly optimized (eg
memchr for searching etc...)
- No way to "GC-dup" the RCString. giving "dup"/"idup" members on
RCstring, for when you really just need to revert to pure un-collected GC.
Nice. But then I'm thinking, wouldn't people think .dup produces another
RCString?
Yes, most likely. How about "gcDup" or something like that.
--
/Jacob Carlborg
Robert burner Schadek via Digitalmars-d
2014-09-15 09:53:25 UTC
Permalink
On Monday, 15 September 2014 at 02:26:19 UTC, Andrei Alexandrescu
Post by Andrei Alexandrescu via Digitalmars-d
The road there is long, but it starts with the proverbial first
step. As it were, I have a rough draft of a almost-drop-in
replacement of string (aka immutable(char)[]). Destroy with
http://dpaste.dzfl.pl/817283c163f5
I haven't found a single lock, is single threading by design or
is thread-safety on your todo?

Could you transfer this into phobos and make it work with the
functions in std.string, it would be a shame if they wouldn't
work out of the box when this gets merged. I haven't seen
anything that should prevent using the functions of std.string
except isSomeString but that should be no problem to fix. This is
sort of personal to me as most of my PR are in std.string and I
sort of aspire to become the LT for std.string ;-)

I would assume RCString should be faster than string, so could
you provide a benchmark of the two.
Jakob Ovrum via Digitalmars-d
2014-09-15 10:13:27 UTC
Permalink
On Monday, 15 September 2014 at 09:53:28 UTC, Robert burner
Post by Vladimir Panteleev via Digitalmars-d
On Monday, 15 September 2014 at 02:26:19 UTC, Andrei
Post by Andrei Alexandrescu via Digitalmars-d
The road there is long, but it starts with the proverbial
first step. As it were, I have a rough draft of a
almost-drop-in replacement of string (aka immutable(char)[]).
http://dpaste.dzfl.pl/817283c163f5
I haven't found a single lock, is single threading by design or
is thread-safety on your todo?
There's no use of `shared`, so all data involved is TLS.
Robert burner Schadek via Digitalmars-d
2014-09-15 11:53:14 UTC
Permalink
Post by Jakob Ovrum via Digitalmars-d
On Monday, 15 September 2014 at 09:53:28 UTC, Robert burner
Post by Robert burner Schadek via Digitalmars-d
I haven't found a single lock, is single threading by design
or is thread-safety on your todo?
There's no use of `shared`, so all data involved is TLS.
Then it must be made sure that send and receive work properly.
Jakob Ovrum via Digitalmars-d
2014-09-15 12:11:13 UTC
Permalink
On Monday, 15 September 2014 at 11:53:15 UTC, Robert burner
Post by Robert burner Schadek via Digitalmars-d
Post by Jakob Ovrum via Digitalmars-d
On Monday, 15 September 2014 at 09:53:28 UTC, Robert burner
Post by Robert burner Schadek via Digitalmars-d
I haven't found a single lock, is single threading by design
or is thread-safety on your todo?
There's no use of `shared`, so all data involved is TLS.
Then it must be made sure that send and receive work properly.
They do. They only accept shared or immutable arguments (or
arguments with no mutable indirection).
Robert burner Schadek via Digitalmars-d
2014-09-15 12:47:06 UTC
Permalink
Post by Jakob Ovrum via Digitalmars-d
Post by Robert burner Schadek via Digitalmars-d
Post by Jakob Ovrum via Digitalmars-d
There's no use of `shared`, so all data involved is TLS.
Then it must be made sure that send and receive work properly.
They do. They only accept shared or immutable arguments (or
arguments with no mutable indirection).
compiler says no: concurrency.d(554): Error: static assert
"Aliases to mutable thread-local data not allowed."

I used the std.concurrency example
Jakob Ovrum via Digitalmars-d
2014-09-15 13:13:32 UTC
Permalink
On Monday, 15 September 2014 at 12:47:08 UTC, Robert burner
Post by Robert burner Schadek via Digitalmars-d
Post by Jakob Ovrum via Digitalmars-d
Post by Robert burner Schadek via Digitalmars-d
Post by Jakob Ovrum via Digitalmars-d
There's no use of `shared`, so all data involved is TLS.
Then it must be made sure that send and receive work properly.
They do. They only accept shared or immutable arguments (or
arguments with no mutable indirection).
compiler says no: concurrency.d(554): Error: static assert
"Aliases to mutable thread-local data not allowed."
I used the std.concurrency example
Yes, that was my point. std.concurrency handles it correctly -
there's no unsafe memory sharing going on with RCString's
implementation.

If you are suggesting we somehow make this work so it can be a
drop-in replacement for `string`:

I don't think that should be implicitly supported.

One method would be to support shared(RCString). This isn't very
practical for this use-case, as since atomic reference counting
is super slow, you wouldn't want to be using shared(RCString)
throughout your program. So you'd have to make a copy on each
side (unshared -> shared, then send, then shared -> unshared)
which is one copy more than necessary and would still require
support for shared(RCString) which is non-trivial.

Another option would be to hardcode support for RCString in
std.concurrency. This would make the copy hidden, which would go
against good practices concerning arrays in D, and not very
useful for @nogc if the copy has to be a GC copy. Additionally,
RCString's interface would need to be compromised to allow
constructing from an existing buffer somehow.

Maybe the right solution involves integration with
std.typecons.Unique. Passing an instance of Unique!T to another
thread is something std.concurrency should support, and RCString
could be given a method that returns Unique!RCString if the
reference count is 1 and errors otherwise. Unique's current
implementation would have to be overhauled to carry its payload
in-situ instead of on the GC heap like it currently does, but
that's something we should do regardless.
Robert burner Schadek via Digitalmars-d
2014-09-15 13:26:31 UTC
Permalink
Post by Jakob Ovrum via Digitalmars-d
If you are suggesting we somehow make this work so it can be a
Yes, you must be able to get a RCString from one thread to the
next.
Post by Jakob Ovrum via Digitalmars-d
I don't think that should be implicitly supported.
Well, it should be at least supported in phobos.

How is another matter.
Post by Jakob Ovrum via Digitalmars-d
Maybe the right solution involves integration with
std.typecons.Unique. Passing an instance of Unique!T to another
thread is something std.concurrency should support, and
RCString could be given a method that returns Unique!RCString
if the reference count is 1 and errors otherwise. Unique's
current implementation would have to be overhauled to carry its
payload in-situ instead of on the GC heap like it currently
does, but that's something we should do regardless.
Sounds good.
Andrei Alexandrescu via Digitalmars-d
2014-09-15 14:53:47 UTC
Permalink
Post by Jakob Ovrum via Digitalmars-d
One method would be to support shared(RCString). This isn't very
practical for this use-case, as since atomic reference counting is super
slow, you wouldn't want to be using shared(RCString) throughout your
program. So you'd have to make a copy on each side (unshared -> shared,
then send, then shared -> unshared) which is one copy more than
necessary and would still require support for shared(RCString) which is
non-trivial.
I think shared(RCString) should be supported. Unique!T is, of course,
also worth exploring. -- Andrei
Sean Kelly via Digitalmars-d
2014-09-15 18:24:07 UTC
Permalink
On Monday, 15 September 2014 at 12:47:08 UTC, Robert burner
Post by Robert burner Schadek via Digitalmars-d
Post by Jakob Ovrum via Digitalmars-d
Post by Robert burner Schadek via Digitalmars-d
Post by Jakob Ovrum via Digitalmars-d
There's no use of `shared`, so all data involved is TLS.
Then it must be made sure that send and receive work properly.
They do. They only accept shared or immutable arguments (or
arguments with no mutable indirection).
compiler says no: concurrency.d(554): Error: static assert
"Aliases to mutable thread-local data not allowed."
I used the std.concurrency example
Probably because RCString is only logically immutable--it
contains unions of mutable and immutable members to simplify
construction.
Andrei Alexandrescu via Digitalmars-d
2014-09-15 14:49:30 UTC
Permalink
Post by Andrei Alexandrescu via Digitalmars-d
The road there is long, but it starts with the proverbial first step.
As it were, I have a rough draft of a almost-drop-in replacement of
http://dpaste.dzfl.pl/817283c163f5
I haven't found a single lock, is single threading by design or is
thread-safety on your todo?
Currently shared strings are not addressed.
Could you transfer this into phobos and make it work with the functions
in std.string, it would be a shame if they wouldn't work out of the box
when this gets merged. I haven't seen anything that should prevent using
the functions of std.string except isSomeString but that should be no
problem to fix.
Good idea.
This is sort of personal to me as most of my PR are in
std.string and I sort of aspire to become the LT for std.string ;-)
Oooh, nice!
I would assume RCString should be faster than string, so could you
provide a benchmark of the two.
Good idea. It likely won't be faster for the most part (unless it uses
realloc and realloc is a lot faster than GC.realloc). Designs based on
RCString will, however, have a tighter memory footprint.


Andrei
Rainer Schuetze via Digitalmars-d
2014-09-15 15:58:17 UTC
Permalink
Post by Andrei Alexandrescu via Digitalmars-d
I haven't found a single lock, is single threading by design or is
thread-safety on your todo?
Currently shared strings are not addressed.
Please also consider usage with const and immutable:

* both will disallow changing the reference count without casting

* immutable means implicitely shared between threads, so you'll have to
make RCString thread-safe even if shared isn't explicitly supported.

Unfortunately, I've yet to see an efficient thread-safe implementation
of reference counting (i.e. without locks).

VC used to have reference counted strings, but moved away from it. Maybe
it doesn't pull its own weight in the face of the small-string-optimization.
Andrei Alexandrescu via Digitalmars-d
2014-09-15 16:22:42 UTC
Permalink
Post by Rainer Schuetze via Digitalmars-d
Post by Andrei Alexandrescu via Digitalmars-d
I haven't found a single lock, is single threading by design or is
thread-safety on your todo?
Currently shared strings are not addressed.
* both will disallow changing the reference count without casting
I think these work fine. If not, please send examples.
Post by Rainer Schuetze via Digitalmars-d
* immutable means implicitely shared between threads, so you'll have to
make RCString thread-safe even if shared isn't explicitly supported.
Hmmm, good point. That's a bug. Immutable postblit and dtors should use
atomic ops.
Post by Rainer Schuetze via Digitalmars-d
Unfortunately, I've yet to see an efficient thread-safe implementation
of reference counting (i.e. without locks).
No locks needed, just interlocked ++/--.
Post by Rainer Schuetze via Digitalmars-d
VC used to have reference counted strings, but moved away from it. Maybe
it doesn't pull its own weight in the face of the
small-string-optimization.
The reason of C++ strings moving away from refcounting is not strongly
related to interlocked refcounting being slow.


Andrei
Rainer Schuetze via Digitalmars-d
2014-09-15 16:56:52 UTC
Permalink
Post by Andrei Alexandrescu via Digitalmars-d
Post by Rainer Schuetze via Digitalmars-d
Post by Andrei Alexandrescu via Digitalmars-d
I haven't found a single lock, is single threading by design or is
thread-safety on your todo?
Currently shared strings are not addressed.
* both will disallow changing the reference count without casting
I think these work fine. If not, please send examples.
Hmm, seems fine when I try it. It feels like a bug in the type system,
though: when you make a copy of const(RCXString) to some RCXString, it
removes the const from the referenced RCBuffer struct mbuf!?
Post by Andrei Alexandrescu via Digitalmars-d
Post by Rainer Schuetze via Digitalmars-d
* immutable means implicitely shared between threads, so you'll have to
make RCString thread-safe even if shared isn't explicitly supported.
Hmmm, good point. That's a bug. Immutable postblit and dtors should use
atomic ops.
Post by Rainer Schuetze via Digitalmars-d
Unfortunately, I've yet to see an efficient thread-safe implementation
of reference counting (i.e. without locks).
No locks needed, just interlocked ++/--.
Eager reference counting with atomics is not thread safe. See the
discussions about automatic reference counting.
Post by Andrei Alexandrescu via Digitalmars-d
Post by Rainer Schuetze via Digitalmars-d
VC used to have reference counted strings, but moved away from it. Maybe
it doesn't pull its own weight in the face of the
small-string-optimization.
The reason of C++ strings moving away from refcounting is not strongly
related to interlocked refcounting being slow.
Yes, they did not care for thread safety back then. IIRC they had no
small-buffer-optimization. With that, reference counting only kicks in
with large strings.

If we need a lock on these for proper reference counting, it's still
better than making a copy including a global lock by the allocator.

Rainer
Andrei Alexandrescu via Digitalmars-d
2014-09-15 17:24:12 UTC
Permalink
Post by Rainer Schuetze via Digitalmars-d
Post by Andrei Alexandrescu via Digitalmars-d
Post by Rainer Schuetze via Digitalmars-d
Post by Andrei Alexandrescu via Digitalmars-d
I haven't found a single lock, is single threading by design or is
thread-safety on your todo?
Currently shared strings are not addressed.
* both will disallow changing the reference count without casting
I think these work fine. If not, please send examples.
Hmm, seems fine when I try it. It feels like a bug in the type system,
though: when you make a copy of const(RCXString) to some RCXString, it
removes the const from the referenced RCBuffer struct mbuf!?
The conversion relies on pure constructors. As I noted in the opening
post, I also think there's something too lax in there. If you have a
reduced example that shows a type system breakage without cast, please
submit.
Post by Rainer Schuetze via Digitalmars-d
Post by Andrei Alexandrescu via Digitalmars-d
Post by Rainer Schuetze via Digitalmars-d
* immutable means implicitely shared between threads, so you'll have to
make RCString thread-safe even if shared isn't explicitly supported.
Hmmm, good point. That's a bug. Immutable postblit and dtors should use
atomic ops.
Post by Rainer Schuetze via Digitalmars-d
Unfortunately, I've yet to see an efficient thread-safe implementation
of reference counting (i.e. without locks).
No locks needed, just interlocked ++/--.
Eager reference counting with atomics is not thread safe. See the
discussions about automatic reference counting.
I'm not sure about that discussion, but there's good evidence from C++
that refcounting with atomics works. What was the smoking gun?


Andrei
via Digitalmars-d
2014-09-15 17:56:54 UTC
Permalink
On Monday, 15 September 2014 at 17:23:32 UTC, Andrei Alexandrescu
Post by Andrei Alexandrescu via Digitalmars-d
I'm not sure about that discussion, but there's good evidence
from C++ that refcounting with atomics works. What was the
smoking gun?
http://www.gotw.ca/gotw/045.htm
po via Digitalmars-d
2014-09-15 18:08:29 UTC
Permalink
Post by via Digitalmars-d
Post by Andrei Alexandrescu via Digitalmars-d
I'm not sure about that discussion, but there's good evidence
from C++ that refcounting with atomics works. What was the
smoking gun?
http://www.gotw.ca/gotw/045.htm
I don't see how that link answers Andrei's question? He just
compares different methods of implementing COW.
Ola Fosheim Gr via Digitalmars-d
2014-09-15 18:31:15 UTC
Permalink
Post by po via Digitalmars-d
Post by via Digitalmars-d
Post by Andrei Alexandrescu via Digitalmars-d
I'm not sure about that discussion, but there's good evidence
from C++ that refcounting with atomics works. What was the
smoking gun?
http://www.gotw.ca/gotw/045.htm
I don't see how that link answers Andrei's question? He just
compares different methods of implementing COW.
As I understand the issue it works if you make sure to transfer
ownership explicitly before the other thread gains access?

Maybe this is more clear:

http://www.1024cores.net/home/lock-free-algorithms/object-life-time-management/differential-reference-counting
po via Digitalmars-d
2014-09-15 19:43:41 UTC
Permalink
Post by Ola Fosheim Gr via Digitalmars-d
As I understand the issue it works if you make sure to transfer
ownership explicitly before the other thread gains access?
http://www.1024cores.net/home/lock-free-algorithms/object-life-time-management/differential-reference-counting
Ah, I think I follow.

So in C++ terms:
It basically requires either a global shared_ptr, or that you
passed one around by reference between threads. And that you then
killed it in one thread at the exact moment the control block was
read in another thread. That blog post discusses a solution, I
wonder if that is implemented in C++'s shared_ptr?
Ola Fosheim Gr via Digitalmars-d
2014-09-15 20:42:28 UTC
Permalink
Post by po via Digitalmars-d
Ah, I think I follow.
It basically requires either a global shared_ptr, or that you
passed one around by reference between threads. And that you
then killed it in one thread at the exact moment the control
block was read in another thread. That blog post discusses a
solution, I wonder if that is implemented in C++'s shared_ptr?
I think you need to either have multiple shared_ptr objects
(owned by threads) or use atomic_* in cpp?

If I got this right for regular RC you have to increment the
refcount before handing it to the other thread who is then
responsible for decrementing it, but if the reference is obtained
through a global datastructure you need the strong semantics in
the blog post at 1024cores since you need to increase the count
to take (thread) ownership of it before accessing it?

(I could be wrong.)
Andrei Alexandrescu via Digitalmars-d
2014-09-16 04:49:47 UTC
Permalink
Post by po via Digitalmars-d
Post by Ola Fosheim Gr via Digitalmars-d
As I understand the issue it works if you make sure to transfer
ownership explicitly before the other thread gains access?
http://www.1024cores.net/home/lock-free-algorithms/object-life-time-management/differential-reference-counting
Ah, I think I follow.
It basically requires either a global shared_ptr, or that you passed
one around by reference between threads. And that you then killed it in
one thread at the exact moment the control block was read in another
thread. That blog post discusses a solution, I wonder if that is
implemented in C++'s shared_ptr?
No, and it neeedn't. The article is not that good. In C++, if a thread
must increment a reference counter while it's going to zero due to
another thread, that's 100% a programming error, not a concurrency
error. That's a well known and well studied problem. As an aside,
searching the net for differential reference counting yields pretty much
only this article.


Andrei
Rainer Schuetze via Digitalmars-d
2014-09-16 05:22:12 UTC
Permalink
Post by Andrei Alexandrescu via Digitalmars-d
Post by po via Digitalmars-d
Post by Ola Fosheim Gr via Digitalmars-d
As I understand the issue it works if you make sure to transfer
ownership explicitly before the other thread gains access?
http://www.1024cores.net/home/lock-free-algorithms/object-life-time-management/differential-reference-counting
Ah, I think I follow.
It basically requires either a global shared_ptr, or that you passed
one around by reference between threads. And that you then killed it in
one thread at the exact moment the control block was read in another
thread. That blog post discusses a solution, I wonder if that is
implemented in C++'s shared_ptr?
No, and it neeedn't. The article is not that good. In C++, if a thread
must increment a reference counter while it's going to zero due to
another thread, that's 100% a programming error, not a concurrency
error. That's a well known and well studied problem. As an aside,
searching the net for differential reference counting yields pretty much
only this article.
Huuh? So you must not read a reference to a ref-counted object that
might get changed in another thread? Maybe you mean destruction of the
shared pointer?

Please note that the scenario is also described by Richard Jones in his
2nd edition of the "Handbook of Garbage Collection" (see algorithm 18.2
"Eager reference counting with CompareAndSwap is broken").
Andrei Alexandrescu via Digitalmars-d
2014-09-16 07:44:29 UTC
Permalink
Post by Rainer Schuetze via Digitalmars-d
Post by Andrei Alexandrescu via Digitalmars-d
Post by po via Digitalmars-d
Post by Ola Fosheim Gr via Digitalmars-d
As I understand the issue it works if you make sure to transfer
ownership explicitly before the other thread gains access?
http://www.1024cores.net/home/lock-free-algorithms/object-life-time-management/differential-reference-counting
Ah, I think I follow.
It basically requires either a global shared_ptr, or that you passed
one around by reference between threads. And that you then killed it in
one thread at the exact moment the control block was read in another
thread. That blog post discusses a solution, I wonder if that is
implemented in C++'s shared_ptr?
No, and it neeedn't. The article is not that good. In C++, if a thread
must increment a reference counter while it's going to zero due to
another thread, that's 100% a programming error, not a concurrency
error. That's a well known and well studied problem. As an aside,
searching the net for differential reference counting yields pretty much
only this article.
Huuh? So you must not read a reference to a ref-counted object that
might get changed in another thread?
I didn't say that.
Post by Rainer Schuetze via Digitalmars-d
Maybe you mean destruction of the
shared pointer?
I meant: by the time the smart pointer got to the thread, its reference
count has increased already.
Post by Rainer Schuetze via Digitalmars-d
Please note that the scenario is also described by Richard Jones in his
2nd edition of the "Handbook of Garbage Collection" (see algorithm 18.2
"Eager reference counting with CompareAndSwap is broken").
I agree such a problem may occur in code generated automatically under
the wraps for high-level languages, but not with shared_ptr (or COM
objects etc).


Andrei
Rainer Schuetze via Digitalmars-d
2014-09-16 15:40:36 UTC
Permalink
Post by Andrei Alexandrescu via Digitalmars-d
Post by Rainer Schuetze via Digitalmars-d
Post by Andrei Alexandrescu via Digitalmars-d
Post by po via Digitalmars-d
Post by Ola Fosheim Gr via Digitalmars-d
As I understand the issue it works if you make sure to transfer
ownership explicitly before the other thread gains access?
http://www.1024cores.net/home/lock-free-algorithms/object-life-time-management/differential-reference-counting
Ah, I think I follow.
It basically requires either a global shared_ptr, or that you passed
one around by reference between threads. And that you then killed it in
one thread at the exact moment the control block was read in another
thread. That blog post discusses a solution, I wonder if that is
implemented in C++'s shared_ptr?
No, and it neeedn't. The article is not that good. In C++, if a thread
must increment a reference counter while it's going to zero due to
another thread, that's 100% a programming error, not a concurrency
error. That's a well known and well studied problem. As an aside,
searching the net for differential reference counting yields pretty much
only this article.
Here is a link with a discussion, links and code:

https://groups.google.com/forum/#!topic/comp.programming.threads/6mXgQEiAOW8

It seems there were multiple patents claiming invention of that technique.
Post by Andrei Alexandrescu via Digitalmars-d
Post by Rainer Schuetze via Digitalmars-d
Huuh? So you must not read a reference to a ref-counted object that
might get changed in another thread?
I didn't say that.
Post by Rainer Schuetze via Digitalmars-d
Maybe you mean destruction of the
shared pointer?
I meant: by the time the smart pointer got to the thread, its reference
count has increased already.
This works if you use message passing. The issue exists for
"shared(shared_ptr!T)". It might be bad style, but that is a convention
not enforced by the language.

Incidentally, Herb Sutter used "shared_ptr<T>" as a means to implement
lock-free linked lists in his talk at the CppCon. To avoid issues, the
list head has to be "atomic<shared_ptr<T>>". Which currently needs a
lock to do an assignment for similar reasons. ;-o He said there might be
ways around that...
Post by Andrei Alexandrescu via Digitalmars-d
Post by Rainer Schuetze via Digitalmars-d
Please note that the scenario is also described by Richard Jones in his
2nd edition of the "Handbook of Garbage Collection" (see algorithm 18.2
"Eager reference counting with CompareAndSwap is broken").
I agree such a problem may occur in code generated automatically under
the wraps for high-level languages, but not with shared_ptr (or COM
objects etc).
I agree it is worse if the mechanism is hidden by the system, pretending
you are dealing with a single pointer. I'm not yet ready to accept it
doesn't exist elsewhere.

Coming back to RCString, immutable(RCString) does not have this problem,
because it must not be modified by any thread. Working with
shared(RCString) isn't supported without a lot of overloads, so you'll
have to synchronize externally and cast away shared.
Kagamin via Digitalmars-d
2014-09-16 09:00:26 UTC
Permalink
On Tuesday, 16 September 2014 at 05:22:15 UTC, Rainer Schuetze
Post by Rainer Schuetze via Digitalmars-d
Huuh? So you must not read a reference to a ref-counted object
that might get changed in another thread?
A slice is two words, concurrently reading and writing them is
not thread-safe in current GC model too, as another thread can
get in between writing length and ptr fields, so it's not a new
behavior.
po via Digitalmars-d
2014-09-16 14:58:21 UTC
Permalink
Post by Andrei Alexandrescu via Digitalmars-d
No, and it neeedn't. The article is not that good. In C++, if a
thread must increment a reference counter while it's going to
zero due to another thread, that's 100% a programming error,
not a concurrency error. That's a well known and well studied
problem. As an aside, searching the net for differential
reference counting yields pretty much only this article.
Andrei
Alright sounds sensible enough, it does seem like you would have
to write some crappy code to trigger it
Rainer Schuetze via Digitalmars-d
2014-09-15 23:41:26 UTC
Permalink
Post by Ola Fosheim Gr via Digitalmars-d
Post by via Digitalmars-d
Post by Andrei Alexandrescu via Digitalmars-d
I'm not sure about that discussion, but there's good evidence from
C++ that refcounting with atomics works. What was the smoking gun?
http://www.gotw.ca/gotw/045.htm
I don't see how that link answers Andrei's question? He just compares
different methods of implementing COW.
As I understand the issue it works if you make sure to transfer
ownership explicitly before the other thread gains access?
http://www.1024cores.net/home/lock-free-algorithms/object-life-time-management/differential-reference-counting
This describes the scenario I meant in the ARC discussions.

Thanks for the link, I didn't know a solution exists. I'll have to study
the "differential" approach to see if it works for our case and at what
cost it comes...
Ola Fosheim Grostad via Digitalmars-d
2014-09-16 04:19:44 UTC
Permalink
On Monday, 15 September 2014 at 23:41:27 UTC, Rainer Schuetze
Post by Rainer Schuetze via Digitalmars-d
Thanks for the link, I didn't know a solution exists. I'll have
to study the "differential" approach to see if it works for our
case and at what cost it comes...
Modern x86 has 128 bit CAS instruction too: lock cmpxchg16b
Sean Kelly via Digitalmars-d
2014-09-16 14:22:03 UTC
Permalink
On Tuesday, 16 September 2014 at 04:19:45 UTC, Ola Fosheim
Post by Ola Fosheim Grostad via Digitalmars-d
On Monday, 15 September 2014 at 23:41:27 UTC, Rainer Schuetze
Post by Rainer Schuetze via Digitalmars-d
Thanks for the link, I didn't know a solution exists. I'll
have to study the "differential" approach to see if it works
for our case and at what cost it comes...
Modern x86 has 128 bit CAS instruction too: lock cmpxchg16b
... which I really need to add to core.atomic.
Andrei Alexandrescu via Digitalmars-d
2014-09-16 15:32:04 UTC
Permalink
Post by Ola Fosheim Grostad via Digitalmars-d
Post by Rainer Schuetze via Digitalmars-d
Thanks for the link, I didn't know a solution exists. I'll have to
study the "differential" approach to see if it works for our case and
at what cost it comes...
Modern x86 has 128 bit CAS instruction too: lock cmpxchg16b
.... which I really need to add to core.atomic.
Yes please. -- Andrei
Rainer Schuetze via Digitalmars-d
2014-09-15 23:49:51 UTC
Permalink
Post by Andrei Alexandrescu via Digitalmars-d
Post by Rainer Schuetze via Digitalmars-d
Hmm, seems fine when I try it. It feels like a bug in the type system,
though: when you make a copy of const(RCXString) to some RCXString, it
removes the const from the referenced RCBuffer struct mbuf!?
The conversion relies on pure constructors. As I noted in the opening
post, I also think there's something too lax in there. If you have a
reduced example that shows a type system breakage without cast, please
submit.
Here's an example:

module module2;

struct S
{
union
{
immutable(char)* iptr;
char* ptr;
}
}

void main()
{
auto s = immutable(S)("hi".ptr);
S t = s;
t.ptr[0] = 'A';
}

It seems the union is hiding the fact that there are mutable references.
Only the first field is verified when copying the struct. Is this by
design? (typeof(s.ptr) is "immutable(char*)")
Andrei Alexandrescu via Digitalmars-d
2014-09-16 15:38:01 UTC
Permalink
Post by Rainer Schuetze via Digitalmars-d
Post by Andrei Alexandrescu via Digitalmars-d
Post by Rainer Schuetze via Digitalmars-d
Hmm, seems fine when I try it. It feels like a bug in the type system,
though: when you make a copy of const(RCXString) to some RCXString, it
removes the const from the referenced RCBuffer struct mbuf!?
The conversion relies on pure constructors. As I noted in the opening
post, I also think there's something too lax in there. If you have a
reduced example that shows a type system breakage without cast, please
submit.
module module2;
struct S
{
union
{
immutable(char)* iptr;
char* ptr;
}
}
void main()
{
auto s = immutable(S)("hi".ptr);
S t = s;
t.ptr[0] = 'A';
}
It seems the union is hiding the fact that there are mutable references.
Only the first field is verified when copying the struct. Is this by
design? (typeof(s.ptr) is "immutable(char*)")
Not sure whether that's a bug or feature :o). In fact I'm not even
kidding. The "it's a bug" view is obvious. The "it's a feature" view
goes by the reasoning: if you're using a union, it means you plan to do
gnarly things with the type system anyway, so the compiler may as well
tread carefully around you.

Through a rather interesting coincidence, I was talking to Walter during
the weekend about the idiom:

union
{
immutable T data;
T mdata;
}

which I found useful for things like incrementing the reference counter
for non-mutable data. I was discussing how it would be cool if the
compiler recognized the construct and did something interesting about
it. It seems it already does.


Andrei
Rainer Schuetze via Digitalmars-d
2014-09-21 09:53:01 UTC
Permalink
Post by Andrei Alexandrescu via Digitalmars-d
Post by Rainer Schuetze via Digitalmars-d
Post by Andrei Alexandrescu via Digitalmars-d
Post by Rainer Schuetze via Digitalmars-d
Hmm, seems fine when I try it. It feels like a bug in the type system,
though: when you make a copy of const(RCXString) to some RCXString, it
removes the const from the referenced RCBuffer struct mbuf!?
The conversion relies on pure constructors. As I noted in the opening
post, I also think there's something too lax in there. If you have a
reduced example that shows a type system breakage without cast, please
submit.
module module2;
struct S
{
union
{
immutable(char)* iptr;
char* ptr;
}
}
void main()
{
auto s = immutable(S)("hi".ptr);
S t = s;
t.ptr[0] = 'A';
}
It seems the union is hiding the fact that there are mutable references.
Only the first field is verified when copying the struct. Is this by
design? (typeof(s.ptr) is "immutable(char*)")
Not sure whether that's a bug or feature :o). In fact I'm not even
kidding. The "it's a bug" view is obvious. The "it's a feature" view
goes by the reasoning: if you're using a union, it means you plan to do
gnarly things with the type system anyway, so the compiler may as well
tread carefully around you.
Through a rather interesting coincidence, I was talking to Walter during
union
{
immutable T data;
T mdata;
}
which I found useful for things like incrementing the reference counter
for non-mutable data. I was discussing how it would be cool if the
compiler recognized the construct and did something interesting about
it. It seems it already does.
Andrei
There is already bug report for this:
https://issues.dlang.org/show_bug.cgi?id=12885

It also references the issue why this has been changed pretty recently:
https://issues.dlang.org/show_bug.cgi?id=11257

I'm on the fence whether this is convenient or makes it too easy to
break const "guarantees". It seems strange that you can modify a
const-reference only after you make a copy of the "pointer". ATM I'd
prefer seeing an explicite cast for that.
Timon Gehr via Digitalmars-d
2014-09-21 13:19:41 UTC
Permalink
Post by Rainer Schuetze via Digitalmars-d
https://issues.dlang.org/show_bug.cgi?id=11257
I'm on the fence whether this is convenient or makes it too easy to
break const "guarantees". It seems strange that you can modify a
const-reference only after you make a copy of the "pointer". ATM I'd
prefer seeing an explicite cast for that.
This change is unsound.

import std.variant;

void foo(const(Algebraic!(int*,const(int)*)) x)@safe{
Algebraic!(int*,const(int)*) y=x;
*y.get!(int*)()=2;
}

void main()@safe{
auto x=Algebraic!(int*,const(int)*)(new int);
assert(*x.get!(int*)()==0); // pass
foo(x); // passed as const, so shouldn't change
assert(*x.get!(int*)()==2); // pass!
}
Sean Kelly via Digitalmars-d
2014-09-15 18:28:56 UTC
Permalink
On Monday, 15 September 2014 at 16:22:01 UTC, Andrei Alexandrescu
Post by Andrei Alexandrescu via Digitalmars-d
Post by Rainer Schuetze via Digitalmars-d
* immutable means implicitely shared between threads, so
you'll have to make RCString thread-safe even if shared isn't
explicitly supported.
Hmmm, good point. That's a bug. Immutable postblit and dtors
should use atomic ops.
Post by Rainer Schuetze via Digitalmars-d
Unfortunately, I've yet to see an efficient thread-safe
implementation of reference counting (i.e. without locks).
No locks needed, just interlocked ++/--.
To be fair, you still have to be a bit careful here or things
could be optimized such that data is seen to disappear or change
when it's not expected to. The original boost::shared_ptr used
an atomic integer as an internal refcount, and that's probably a
good template for how to do RC here. The newer implementation is
a lot fancier with spinlocks and such, I believe, and is a lot
more complicated.

Also... this is why I'm not over-fond of having immutable being
implicitly shared. Being unable to create an efficient RCString
that I know is thread-local (the normal case) kind of stinks.
Maybe there can be a
template parameter option along these lines?
Andrei Alexandrescu via Digitalmars-d
2014-09-15 18:41:06 UTC
Permalink
Post by Sean Kelly via Digitalmars-d
On Monday, 15 September 2014 at 16:22:01 UTC, Andrei Alexandrescu
Post by Andrei Alexandrescu via Digitalmars-d
Post by Rainer Schuetze via Digitalmars-d
* immutable means implicitely shared between threads, so you'll have
to make RCString thread-safe even if shared isn't explicitly supported.
Hmmm, good point. That's a bug. Immutable postblit and dtors should
use atomic ops.
Post by Rainer Schuetze via Digitalmars-d
Unfortunately, I've yet to see an efficient thread-safe
implementation of reference counting (i.e. without locks).
No locks needed, just interlocked ++/--.
To be fair, you still have to be a bit careful here or things
could be optimized such that data is seen to disappear or change
when it's not expected to. The original boost::shared_ptr used
an atomic integer as an internal refcount, and that's probably a
good template for how to do RC here. The newer implementation is
a lot fancier with spinlocks and such, I believe, and is a lot
more complicated.
That's news to me. Perhaps it's weak pointer management they need to
address?
Post by Sean Kelly via Digitalmars-d
Also... this is why I'm not over-fond of having immutable being
implicitly shared. Being unable to create an efficient RCString
that I know is thread-local (the normal case) kind of stinks. Maybe
there can be a
template parameter option along these lines?
Non-immutable and non-shared RCStrings are the ticket.


Andrei
Rainer Schuetze via Digitalmars-d
2014-09-15 15:59:22 UTC
Permalink
Post by Andrei Alexandrescu via Digitalmars-d
I would assume RCString should be faster than string, so could you
provide a benchmark of the two.
Good idea. It likely won't be faster for the most part (unless it uses
realloc and realloc is a lot faster than GC.realloc).
Do you have any benchmarks to share? Last time I measured, the GC is
quite a bit faster with manual memory management than the C runtime on
Win32 and on par on Win64.
bearophile via Digitalmars-d
2014-09-15 10:30:21 UTC
Permalink
Post by Andrei Alexandrescu via Digitalmars-d
Walter, Brad, myself, and a couple of others have had a couple
of quite exciting ideas regarding code that is configurable to
use the GC or alternate resource management strategies.
An alternative design solution is to follow the Java way, leave
the D strings as they are, and avoid to make a mess of user D
code. Java GC and runtime contain numerous optimizations for the
management of strings, like the recently introduced string
de-duplication at run-time:

https://blog.codecentric.de/en/2014/08/string-deduplication-new-feature-java-8-update-20-2

Bye,
bearophile
Andrei Alexandrescu via Digitalmars-d
2014-09-15 14:51:11 UTC
Permalink
Post by Andrei Alexandrescu via Digitalmars-d
Walter, Brad, myself, and a couple of others have had a couple of
quite exciting ideas regarding code that is configurable to use the GC
or alternate resource management strategies.
An alternative design solution is to follow the Java way, leave the D
strings as they are, and avoid to make a mess of user D code. Java GC
and runtime contain numerous optimizations for the management of
https://blog.codecentric.de/en/2014/08/string-deduplication-new-feature-java-8-update-20-2
Again, it's become obvious that a category of users will simply refuse
to use a GC, either for the right or the wrong reasons. We must make D
eminently usable for them.

Andrei
bearophile via Digitalmars-d
2014-09-15 15:07:37 UTC
Permalink
Post by Andrei Alexandrescu via Digitalmars-d
Again, it's become obvious that a category of users will simply
refuse to use a GC, either for the right or the wrong reasons.
We must make D eminently usable for them.
Is adding reference counted strings to D going to add a
significant amount of complexity for the programmers?

As usual your judgement is better than mine, but surely the
increase in complexity of D language and its usage must be
considered in this rcstring discussion. So far I have not seen
this point discussed enough in this thread.

D is currently quite complex, so I prefer enhancements that
simplify the code (like tuples), or that make it safer (this
mostly means type system improvements, like eprovably correct
tracking of memory areas and lifetimes, or stricter types for
array indexes, or better means to detect errors at compile-times
with more compile-time introspection for function/ctor
arguments), or features that have a limited scope and don't
increase the general code complexity much (like the partial type
inference patch created by Kenji).

Bye,
bearophile
Andrei Alexandrescu via Digitalmars-d
2014-09-15 15:31:01 UTC
Permalink
Post by Andrei Alexandrescu via Digitalmars-d
Again, it's become obvious that a category of users will simply refuse
to use a GC, either for the right or the wrong reasons. We must make D
eminently usable for them.
Is adding reference counted strings to D going to add a significant
amount of complexity for the programmers?
Time will tell, but I don't think so.
As usual your judgement is better than mine, but surely the increase in
complexity of D language and its usage must be considered in this
rcstring discussion. So far I have not seen this point discussed enough
in this thread.
Increasing the standard library with good artifacts is important. So is
making it more generic by (in this case) expanding the kinds of strings
it supports.
D is currently quite complex, so I prefer enhancements that simplify the
code (like tuples), or that make it safer (this mostly means type system
improvements, like eprovably correct tracking of memory areas and
lifetimes, or stricter types for array indexes, or better means to
detect errors at compile-times with more compile-time introspection for
function/ctor arguments), or features that have a limited scope and
don't increase the general code complexity much (like the partial type
inference patch created by Kenji).
I think most people exclude the library when discussing the complexity
of a language.


Andrei
Jakob Ovrum via Digitalmars-d
2014-09-15 15:34:53 UTC
Permalink
On Monday, 15 September 2014 at 02:26:19 UTC, Andrei Alexandrescu
Post by Andrei Alexandrescu via Digitalmars-d
http://dpaste.dzfl.pl/817283c163f5
The test on line 267 fails on a 32-bit build:

rcstring.d(267): Error: cannot implicitly convert expression
(38430716820228232L) of type long to uint

Hosting it as a Gist on Github[1] might be an idea, as then the
same link will be relevant after the code is updated, and people
can post line comments. It doesn't support building and running
the code online, but dpaste.dzfl.pl's old FE version (2.065)
doesn't support the code anyway.

[1] https://gist.github.com/
Marco Leise via Digitalmars-d
2014-09-15 18:53:46 UTC
Permalink
Am Mon, 15 Sep 2014 15:34:53 +0000
Post by Vladimir Panteleev via Digitalmars-d
On Monday, 15 September 2014 at 02:26:19 UTC, Andrei Alexandrescu
Post by Andrei Alexandrescu via Digitalmars-d
http://dpaste.dzfl.pl/817283c163f5
rcstring.d(267): Error: cannot implicitly convert expression
(38430716820228232L) of type long to uint
https://issues.dlang.org/show_bug.cgi?id=5063 >.<
--
Marco
Sean Kelly via Digitalmars-d
2014-09-15 18:21:16 UTC
Permalink
On Monday, 15 September 2014 at 02:26:19 UTC, Andrei Alexandrescu
Post by Andrei Alexandrescu via Digitalmars-d
The road there is long, but it starts with the proverbial first
step. As it were, I have a rough draft of a almost-drop-in
replacement of string (aka immutable(char)[]). Destroy with
http://dpaste.dzfl.pl/817283c163f5
So slicing an RCString doesn't increment its refcount?
Andrei Alexandrescu via Digitalmars-d
2014-09-15 18:39:50 UTC
Permalink
Post by Vladimir Panteleev via Digitalmars-d
On Monday, 15 September 2014 at 02:26:19 UTC, Andrei Alexandrescu
Post by Andrei Alexandrescu via Digitalmars-d
The road there is long, but it starts with the proverbial first step.
As it were, I have a rough draft of a almost-drop-in replacement of
http://dpaste.dzfl.pl/817283c163f5
So slicing an RCString doesn't increment its refcount?
It does. -- Andrei
Sean Kelly via Digitalmars-d
2014-09-15 18:40:28 UTC
Permalink
On Monday, 15 September 2014 at 18:39:09 UTC, Andrei Alexandrescu
Post by Andrei Alexandrescu via Digitalmars-d
Post by Vladimir Panteleev via Digitalmars-d
On Monday, 15 September 2014 at 02:26:19 UTC, Andrei
Alexandrescu
Post by Andrei Alexandrescu via Digitalmars-d
The road there is long, but it starts with the proverbial
first step.
As it were, I have a rough draft of a almost-drop-in
replacement of
string (aka immutable(char)[]). Destroy with maximum
http://dpaste.dzfl.pl/817283c163f5
So slicing an RCString doesn't increment its refcount?
It does. -- Andrei
Oops, I was looking at the opSlice for Large, not RCString.
Dicebot via Digitalmars-d
2014-09-17 16:30:08 UTC
Permalink
On Monday, 15 September 2014 at 02:26:19 UTC, Andrei Alexandrescu
Post by Andrei Alexandrescu via Digitalmars-d
Walter, Brad, myself, and a couple of others have had a couple
of quite exciting ideas regarding code that is configurable to
use the GC or alternate resource management strategies. One
thing that became obvious to us is we need to have a reference
counted string in the standard library. That would be usable
with applications that want to benefit from comfortable string
manipulation whilst using classic reference counting for memory
management. I'll get into more details into the mechanisms that
would allow the stdlib to provide functionality for both GC
strings and RC strings; for now let's say that we hope and aim
for swapping between these with ease. We hope that at one point
people would be able to change one line of code, rebuild, and
get either GC or RC automatically (for Phobos and their own
code).
Ironically, strings have been probably least of my GC-related
issues with D so far - hard to evaluate applicability of this
proposal because of that. What are typical use cases for such
solution? (not questioning its importance, just being curious)
Andrei Alexandrescu via Digitalmars-d
2014-09-17 16:32:42 UTC
Permalink
Ironically, strings have been probably least of my GC-related issues
with D so far - hard to evaluate applicability of this proposal because
of that. What are typical use cases for such solution? (not questioning
its importance, just being curious)
Simplest is "I want to use D without a GC and suddenly the string
support has fallen down to bear claws and silex stones."

RCString should be a transparent (or at least near-transparent)
replacement for string in GC-less environments.


Andrei
Piotrek via Digitalmars-d
2014-09-17 21:12:08 UTC
Permalink
On Wednesday, 17 September 2014 at 16:32:41 UTC, Andrei
Post by Andrei Alexandrescu via Digitalmars-d
Post by Dicebot via Digitalmars-d
Ironically, strings have been probably least of my GC-related
issues
with D so far - hard to evaluate applicability of this
proposal because
of that. What are typical use cases for such solution? (not
questioning
its importance, just being curious)
Simplest is "I want to use D without a GC and suddenly the
string support has fallen down to bear claws and silex stones."
RCString should be a transparent (or at least near-transparent)
replacement for string in GC-less environments.
Andrei
I think the biggest gc=(partially?)off customers are game makers:

http://forum.dlang.org/thread/k27bh7$t7f$1 at digitalmars.com

(check especially the bottom of the 6th page)

Random quote:
"I created a reference counted array which is as close to the
native D
array as currently possible (compiler bugs, type system issues,
etc).
also in core.refcounted. It however does not replace the default
string
or array type in all cases because it would lead to reference
counting
in uneccessary places. The focus is to get only reference couting
where
absolutly neccessary. I'm still using the standard string type as
a
"only valid for current scope" kind of string."

And my fav:
"- You most likely won't like the way I implemented reference
counting"

I hope Benjamin Thaut can share his viewpoint on the topic if he
is still around.

Piotrek
Dicebot via Digitalmars-d
2014-09-19 10:32:37 UTC
Permalink
On Wednesday, 17 September 2014 at 16:32:41 UTC, Andrei
Post by Andrei Alexandrescu via Digitalmars-d
Post by Dicebot via Digitalmars-d
Ironically, strings have been probably least of my GC-related
issues
with D so far - hard to evaluate applicability of this
proposal because
of that. What are typical use cases for such solution? (not
questioning
its importance, just being curious)
Simplest is "I want to use D without a GC and suddenly the
string support has fallen down to bear claws and silex stones."
RCString should be a transparent (or at least near-transparent)
replacement for string in GC-less environments.
Well this is exactly what I don't understand. Strings we have
don't have any strong connection to GC (apart from concatenation
which can be verified by @nogc) being just slices to some
external buffer. That buffer can be malloc'ed or stack allocated,
that doesn't really affect most string processing algorithms, not
unless those try to do some re-allocation of their own.

I agree that pipeline approach does not work that well for
complex programs in general but strings seem to be best match to
it - either you want read-only access or a pipe-line, everything
else feels inefficient as amount of write operations gets out of
control. Every single attempt to do something clever with shared
CoW strings in C++ I have met was a total failure.

That is why I wonder - what kind of applications really need the
rcstring as opposed to some generic rcarray?
Andrei Alexandrescu via Digitalmars-d
2014-09-19 15:09:41 UTC
Permalink
Post by Andrei Alexandrescu via Digitalmars-d
Ironically, strings have been probably least of my GC-related issues
with D so far - hard to evaluate applicability of this proposal because
of that. What are typical use cases for such solution? (not questioning
its importance, just being curious)
Simplest is "I want to use D without a GC and suddenly the string
support has fallen down to bear claws and silex stones."
RCString should be a transparent (or at least near-transparent)
replacement for string in GC-less environments.
Well this is exactly what I don't understand. Strings we have don't have
any strong connection to GC (apart from concatenation which can be
buffer can be malloc'ed or stack allocated, that doesn't really affect
most string processing algorithms, not unless those try to do some
re-allocation of their own.
It does affect management, i.e. you don't know when to free the buffer
if slices are unaccounted for. So the design of slices are affected as
much as that of the buffer.
I agree that pipeline approach does not work that well for complex
programs in general but strings seem to be best match to it - either you
want read-only access or a pipe-line, everything else feels inefficient
as amount of write operations gets out of control. Every single attempt
to do something clever with shared CoW strings in C++ I have met was a
total failure.
What were the issues?
That is why I wonder - what kind of applications really need the
rcstring as opposed to some generic rcarray?
I started with rcstring because (a) it's easier to lift off the ground -
no worries about construction/destruction of elements etc. and (b) it's
frequent enough to warrant some good testing. Of course there'll be an
rcarray!T as well.


Andrei
Dicebot via Digitalmars-d
2014-09-20 07:42:06 UTC
Permalink
On Friday, 19 September 2014 at 15:09:41 UTC, Andrei Alexandrescu
Post by Andrei Alexandrescu via Digitalmars-d
It does affect management, i.e. you don't know when to free the
buffer if slices are unaccounted for. So the design of slices
are affected as much as that of the buffer.
I see where you are going at. A bit hard to imagine how it fits
the big picture when going bottom-up though but I trust you on
this :)
Post by Andrei Alexandrescu via Digitalmars-d
Post by Dicebot via Digitalmars-d
I agree that pipeline approach does not work that well for
complex
programs in general but strings seem to be best match to it -
either you
want read-only access or a pipe-line, everything else feels
inefficient
as amount of write operations gets out of control. Every
single attempt
to do something clever with shared CoW strings in C++ I have
met was a
total failure.
What were the issues?
Usually it went that way:

1) Get basic implementation, become shocked how slow it is
because of redundant reference increments/decrements and thread
safety
2) Add speed-up hacks to avoid reference count amending when
considered unnecessary
3) Get hit by a snowball of synchronization / double-free issues
and abandon the idea completely after months of debugging.

Of course those weren't teams of rock-star programmers but at the
same time more "stupid" approach with making extra copies and
putting extra effort into defining strict linear ownership chain
seemed to work much better.
Post by Andrei Alexandrescu via Digitalmars-d
Post by Dicebot via Digitalmars-d
That is why I wonder - what kind of applications really need
the
rcstring as opposed to some generic rcarray?
I started with rcstring because (a) it's easier to lift off the
ground - no worries about construction/destruction of elements
etc. and (b) it's frequent enough to warrant some good testing.
Of course there'll be an rcarray!T as well.
Thanks for explanation :) Well, I am curious how will it turn out
but a bit skeptical right now.
Andrei Alexandrescu via Digitalmars-d
2014-09-20 15:30:55 UTC
Permalink
Post by Andrei Alexandrescu via Digitalmars-d
as amount of write operations gets out of control. Every single attempt
to do something clever with shared CoW strings in C++ I have met was a
total failure.
What were the issues?
1) Get basic implementation, become shocked how slow it is because of
redundant reference increments/decrements and thread safety
2) Add speed-up hacks to avoid reference count amending when considered
unnecessary
3) Get hit by a snowball of synchronization / double-free issues and
abandon the idea completely after months of debugging.
I understand. RC strings will work just fine. Compared to interlocked
approaches we're looking at a 5x improvement in RC speed for the most
part because we can dispense with most interlocking. -- Andrei
via Digitalmars-d
2014-09-20 17:55:27 UTC
Permalink
On Saturday, 20 September 2014 at 15:30:55 UTC, Andrei
Post by Andrei Alexandrescu via Digitalmars-d
I understand. RC strings will work just fine. Compared to
interlocked approaches we're looking at a 5x improvement in RC
speed for the most part because we can dispense with most
interlocking. -- Andrei
Can someone explain why?

Since fibers can travel between threads, they will also be able
to leak objects to different threads.
Dmitry Olshansky via Digitalmars-d
2014-09-21 08:24:44 UTC
Permalink
20-Sep-2014 21:55, "Ola Fosheim GrÞstad"
Post by via Digitalmars-d
Post by Andrei Alexandrescu via Digitalmars-d
I understand. RC strings will work just fine. Compared to interlocked
approaches we're looking at a 5x improvement in RC speed for the most
part because we can dispense with most interlocking. -- Andrei
Can someone explain why?
Since fibers can travel between threads, they will also be able to leak
objects to different threads.
Not spontaneously :)
You'd have to cast to shared and back, and then you are on your own.
Fiber is thread-local, shared(Fiber) isn't.
--
Dmitry Olshansky
Ola Fosheim Grostad via Digitalmars-d
2014-09-21 09:06:56 UTC
Permalink
On Sunday, 21 September 2014 at 08:24:46 UTC, Dmitry Olshansky
Post by Dmitry Olshansky via Digitalmars-d
Not spontaneously :)
You'd have to cast to shared and back, and then you are on your own.
Fiber is thread-local, shared(Fiber) isn't.
That will have to change if Go is a target. To get full load you
need to let fibers move freely between threads I think. Go also
check fiber stack size... But maybe Go should not be considered a
target.
Dicebot via Digitalmars-d
2014-09-21 15:21:55 UTC
Permalink
On Sunday, 21 September 2014 at 09:06:57 UTC, Ola Fosheim Grostad
Post by Ola Fosheim Grostad via Digitalmars-d
On Sunday, 21 September 2014 at 08:24:46 UTC, Dmitry Olshansky
Post by Dmitry Olshansky via Digitalmars-d
Not spontaneously :)
You'd have to cast to shared and back, and then you are on
your own.
Fiber is thread-local, shared(Fiber) isn't.
That will have to change if Go is a target. To get full load
you need to let fibers move freely between threads I think. Go
also check fiber stack size... But maybe Go should not be
considered a target.
It doesn't ring a bell to me. For several reasons:

1) Go doesn't seem to be a target right now. There has been
certain examples that D is capable to beat Go in its own domain
(see Atila MQTT broker articles). It may change later but there
has been no experimental confirmations that their approach is
better by design.

2) For good CPU load distribution moving of task is likely to be
needed indeed but it is not necessarily the same thing as moving
fibers and definitely not all need to be moved. I like that
vibe.d goes forward with this by defining own `Task` abstraction
on top of fibers. Thus this is something that belong to specific
task scheduler/manager and not basic Fiber implementation.
Dmitry Olshansky via Digitalmars-d
2014-09-21 17:52:38 UTC
Permalink
Post by Ola Fosheim Grostad via Digitalmars-d
Post by Dmitry Olshansky via Digitalmars-d
Not spontaneously :)
You'd have to cast to shared and back, and then you are on your own.
Fiber is thread-local, shared(Fiber) isn't.
That will have to change if Go is a target.
Go is not a target. The fixed concurrency model the have is not the
silver bullet.
Post by Ola Fosheim Grostad via Digitalmars-d
To get full load you need to
let fibers move freely between threads I think.
Why? The only thing required is scheduling by passing new work-item (a
fiber) to the least loaded thread (or some other strategy). Keeping
thread affinity of Fiber is a boon: you get to use non-atomic
ref-counting and have far less cache pollution (the set of fibers to
switch over is consistent).
Post by Ola Fosheim Grostad via Digitalmars-d
Go also check fiber
stack size... But maybe Go should not be considered a target.
??? Just reserve more space. Even Go dropped segmented stack.
What Go has to do with this discussion at all BTW?
--
Dmitry Olshansky
Ola Fosheim Grostad via Digitalmars-d
2014-09-21 21:45:52 UTC
Permalink
On Sunday, 21 September 2014 at 17:52:42 UTC, Dmitry Olshansky
to use non-atomic ref-counting and have far less cache
pollution (the set of fibers to switch over is consistent).
Caches are not a big deal when you wait for io.
Post by Ola Fosheim Grostad via Digitalmars-d
Go also check fiber
stack size... But maybe Go should not be considered a target.
??? Just reserve more space. Even Go dropped segmented stack.
What Go has to do with this discussion at all BTW?
Because that is what you are competing with in the webspace.

Go checks and extends stacks.
Paulo Pinto via Digitalmars-d
2014-09-21 22:59:02 UTC
Permalink
Post by Ola Fosheim Grostad via Digitalmars-d
Post by Dmitry Olshansky via Digitalmars-d
...
??? Just reserve more space. Even Go dropped segmented stack.
What Go has to do with this discussion at all BTW?
Because that is what you are competing with in the webspace.
Go checks and extends stacks.
Since when Go is a competitor in the webspace?

From all the languages used to develop web applications, Go is not on
top list for most people.

At least on the IT world I am part of.

--
Paulo
Ola Fosheim Grostad via Digitalmars-d
2014-09-21 23:06:11 UTC
Permalink
Post by Paulo Pinto via Digitalmars-d
Since when Go is a competitor in the webspace?
Since people who create high throughput servers started using it?
Paulo Pinto via Digitalmars-d
2014-09-21 23:28:34 UTC
Permalink
Post by Ola Fosheim Grostad via Digitalmars-d
Post by Paulo Pinto via Digitalmars-d
Since when Go is a competitor in the webspace?
Since people who create high throughput servers started using it?
Which people? A few Silicon Valley startups, besides Google?

Around me I see such servers being written in Erlang, JVM and .NET
languages, with the occasional drop to C++ when nothing else goes.

--
Paulo
Ola Fosheim Grostad via Digitalmars-d
2014-09-21 23:47:10 UTC
Permalink
Post by Paulo Pinto via Digitalmars-d
On Sunday, 21 September 2014 at 22:58:59 UTC, Paulo Pinto
Post by Paulo Pinto via Digitalmars-d
Since when Go is a competitor in the webspace?
Since people who create high throughput servers started using
it?
Which people? A few Silicon Valley startups, besides Google?
I am not keeping track, but e.g.
https://www.cloudflare.com/railgun
Post by Paulo Pinto via Digitalmars-d
Around me I see such servers being written in Erlang,
Erlang would be another example.
Googler Lurker via Digitalmars-d
2014-09-22 02:33:59 UTC
Permalink
Post by Paulo Pinto via Digitalmars-d
On Sunday, 21 September 2014 at 22:58:59 UTC, Paulo Pinto
Post by Paulo Pinto via Digitalmars-d
Since when Go is a competitor in the webspace?
Since people who create high throughput servers started using
it?
Which people? A few Silicon Valley startups, besides Google?
Go fizzled inside google but granted has traction outside of
google. Paulo stop feeding the troll for Petes sake.
Ola Fosheim Grostad via Digitalmars-d
2014-09-22 09:45:22 UTC
Permalink
On Monday, 22 September 2014 at 02:34:00 UTC, Googler Lurker
Post by Googler Lurker via Digitalmars-d
Go fizzled inside google but granted has traction outside of
google. Paulo stop feeding the troll for Petes sake.
Don't be such a coward, show your face and publish you real name.
Your style and choice of words reminds me of A.A. Do the man a
favour and clear up this source for confusion.

Locking fibers to threads will cost you more than using
threadsafe features. One 300ms request can then starve waiting
fibers even if you have 7 free threads. That's bad for latency,
because then all fibers on that thread will get 300+ms in latency.

How anyone can disagree with this is beyond me.
Dmitry Olshansky via Digitalmars-d
2014-09-22 19:58:23 UTC
Permalink
Locking fibers to threads will cost you more than using threadsafe
features. One 300ms request can then starve waiting fibers even if you
have 7 free threads.
This statement doesn't make any sense taken in isolation. It lacks way
too much context to be informative. For instance, "locking a thread for
300ms" is easily averted if all I/O and blocking sys-call are managed in
a separate thread pool (that may grow far beyond fiber-scheduled "web"
thread pool).

And if "locked" means CPU-bound locked, then it's
a) hard to fix without help from OS: re-scheduling a fiber without
explicit yield ain't possible (it's cooperative, preemption is in the
domain of OS).

Something like Windows User-Mode Scheduling is required or user-mode
threads a-la FreeBSD (haven't checked in a while?).

b) If CPU-bound is happening more often then once in a while, then
fibers are poor fit anyway - threads (and pools of 'em) do exactly
what's needed in this case by being natively preemptive and well suited
for running multiple CPU intensive tasks.
That's bad for latency, because then all fibers on
that thread will get 300+ms in latency.
E-hm locking threads to fibers and arbitrary latency figures have very
little to do with each other. The nature of that latency is extremely
important.
How anyone can disagree with this is beyond me.
IMHO poorly formed problem statements are not going to prove your point.
Pardon me making a personal statement, but for instance showing how Go
avoids your problem and clearly specifying the exact conditions that
cause it would go a long way to demonstrated whatever you wanted to.
--
Dmitry Olshansky
Dmitry Olshansky via Digitalmars-d
2014-09-22 19:34:46 UTC
Permalink
Post by Ola Fosheim Grostad via Digitalmars-d
to use non-atomic ref-counting and have far less cache pollution (the
set of fibers to switch over is consistent).
Caches are not a big deal when you wait for io.
Post by Ola Fosheim Grostad via Digitalmars-d
Go also check fiber
stack size... But maybe Go should not be considered a target.
??? Just reserve more space. Even Go dropped segmented stack.
What Go has to do with this discussion at all BTW?
Because that is what you are competing with in the webspace.
E-hm Go is hardly the top dog in the web space. Java and JVM crowd like
(Scala etc.) are apparently very sexy (and performant) in the web space.
They try to sell it as if it was all the rage though.

IMO Go is hardly an interesting opponent to compete against. In pretty
much any use case I see Go is somewhere down to 4-th+ place to look at.
Post by Ola Fosheim Grostad via Digitalmars-d
Go checks and extends stacks.
Since 1.2 or 1.3 i.e. relatively new stuff.
--
Dmitry Olshansky
Kagamin via Digitalmars-d
2014-09-21 19:27:57 UTC
Permalink
On Sunday, 21 September 2014 at 09:06:57 UTC, Ola Fosheim Grostad
Post by Ola Fosheim Grostad via Digitalmars-d
That will have to change if Go is a target. To get full load
you need to let fibers move freely between threads I think. Go
also check fiber stack size... But maybe Go should not be
considered a target.
Only isolated cluster can safely migrate between threads. D has
no means to check isolation, you should check it manually, and in
addition check if the logic doesn't depend on tls.
Ola Fosheim Grostad via Digitalmars-d
2014-09-21 21:42:02 UTC
Permalink
Post by Kagamin via Digitalmars-d
Only isolated cluster can safely migrate between threads. D has
no means to check isolation, you should check it manually, and
in addition check if the logic doesn't depend on tls.
This can easily be borked if built in RC does not provide
threadsafety.

If you want low latency, high throughput and low memory overhead,
then you gotta use available threads. Otherwise the load
balancing will be wonky.

Most requests in a web service will wait for network traffic from
memcaches. So a requeston a fober will have to be rescheduled at
least once on average.
Kagamin via Digitalmars-d
2014-09-22 13:06:46 UTC
Permalink
On Sunday, 21 September 2014 at 21:42:03 UTC, Ola Fosheim Grostad
Post by Ola Fosheim Grostad via Digitalmars-d
Post by Kagamin via Digitalmars-d
Only isolated cluster can safely migrate between threads. D
has no means to check isolation, you should check it manually,
and in addition check if the logic doesn't depend on tls.
This can easily be borked if built in RC does not provide
threadsafety.
Isolated data is single-threaded w.r.t. concurrent access. What
thread-safety do you miss? You should only check for
environmental dependencies, which are not strictly related to
concurrency.
&quot;Nordlöw&quot; via Digitalmars-d
2014-09-20 15:21:16 UTC
Permalink
On Monday, 15 September 2014 at 02:26:19 UTC, Andrei Alexandrescu
Post by Andrei Alexandrescu via Digitalmars-d
Andrei
I'm testing your RCstring right now in my code to see how much
memory it will save and speed it will gain. I want to use
RCString in place of string as a key in my AAs. Any proposals for
a suitable implementation of

size_t toHash() @trusted pure nothrow

for RCString? I'm guessing there are two cases here; one for the
SSO-case an one for the other. The other should be similar to

size_t toHash(string) @trusted pure nothrow

right?
&quot;Nordlöw&quot; via Digitalmars-d
2014-09-20 15:54:42 UTC
Permalink
Post by &quot;Nordlöw&quot; via Digitalmars-d
for RCString? I'm guessing there are two cases here;
I'm guessing

size_t toHash() const @trusted pure nothrow
{
import core.internal.hash : hashOf;
if (isSmall)
{
return this.small.hashOf;
}
else
{
return this.large[].hashOf;
}
}

Will

this.large[].hashOf

do unneccessary GC-allocations? -vgc says nothing.

I'm compiling as

dmd -vcolumns -debug -g -gs -vgc -unittest -wi -main
rcstring.d -o rcstring.out
Andrei Alexandrescu via Digitalmars-d
2014-09-20 17:06:48 UTC
Permalink
Post by &quot;Nordlöw&quot; via Digitalmars-d
Post by &quot;Nordlöw&quot; via Digitalmars-d
for RCString? I'm guessing there are two cases here;
I'm guessing
{
import core.internal.hash : hashOf;
if (isSmall)
{
return this.small.hashOf;
}
else
{
return this.large[].hashOf;
}
}
Why not just "return this.asSlice.hashOf;"?
Post by &quot;Nordlöw&quot; via Digitalmars-d
Will
this.large[].hashOf
do unneccessary GC-allocations? -vgc says nothing.
No.


Andrei
&quot;Nordlöw&quot; via Digitalmars-d
2014-09-20 18:01:41 UTC
Permalink
On Saturday, 20 September 2014 at 17:06:48 UTC, Andrei
Post by Andrei Alexandrescu via Digitalmars-d
Why not just "return this.asSlice.hashOf;"?
Good idea :)

I'll use that instead.
Post by Andrei Alexandrescu via Digitalmars-d
Post by &quot;Nordlöw&quot; via Digitalmars-d
Will
this.large[].hashOf
do unneccessary GC-allocations? -vgc says nothing.
Ok, great! A couple of followup questions.

How big overhead is an RC compared to a non-RC GC-free string
variant?

Perhaps it would be nice to add a template parameter in RCXString
that makes the RC-optional?

If I want a *non*-RC GC-free variant of string/wstring/dstring
what's the best way to define them?

Would Array!char, Array!wchar, Array!dchar, be suitable
solutions? Of course these wouldn't utilize SSO. I'm asking
because Array is RandomAccess but string/wstring is not
byCodePoint.
Andrei Alexandrescu via Digitalmars-d
2014-09-20 18:47:59 UTC
Permalink
Post by &quot;Nordlöw&quot; via Digitalmars-d
How big overhead is an RC compared to a non-RC GC-free string
variant?
Ballpark would be probably 1.1-2.5x. But there's of course a bunch of
variability.
Post by &quot;Nordlöw&quot; via Digitalmars-d
Perhaps it would be nice to add a template parameter in RCXString
that makes the RC-optional?
Manual memory management is not part of its charter.
Post by &quot;Nordlöw&quot; via Digitalmars-d
If I want a *non*-RC GC-free variant of string/wstring/dstring
what's the best way to define them?
I think you're back to malloc and free kind of stuff.
Post by &quot;Nordlöw&quot; via Digitalmars-d
Would Array!char, Array!wchar, Array!dchar, be suitable
solutions? Of course these wouldn't utilize SSO. I'm asking
because Array is RandomAccess but string/wstring is not
byCodePoint.
Those are refcounted.


Andrei
Andrei Alexandrescu via Digitalmars-d
2014-09-20 17:07:42 UTC
Permalink
Post by &quot;Nordlöw&quot; via Digitalmars-d
Post by &quot;Nordlöw&quot; via Digitalmars-d
for RCString? I'm guessing there are two cases here;
I'm guessing
{
import core.internal.hash : hashOf;
if (isSmall)
{
return this.small.hashOf;
Oh in fact this.small.hashOf is incorrect anyway because it hashes
random characters after the used portion of the string. -- Andrei
Andrei Alexandrescu via Digitalmars-d
2014-09-20 16:57:50 UTC
Permalink
Post by Andrei Alexandrescu via Digitalmars-d
Andrei
I'm testing your RCstring right now in my code to see how much memory it
will save and speed it will gain.
Thanks!
I want to use RCString in place of
string as a key in my AAs. Any proposals for a suitable implementation of
for RCString? I'm guessing there are two cases here; one for the
SSO-case an one for the other. The other should be similar to
right?
Yah, that's the one.


Andrei
&quot;Nordlöw&quot; via Digitalmars-d
2014-09-20 19:29:16 UTC
Permalink
On Saturday, 20 September 2014 at 16:57:49 UTC, Andrei
Post by Andrei Alexandrescu via Digitalmars-d
Thanks!
Calling writeln(rcstring) in a module other than rcstring.d

gives

immutable(RCXString!(immutable(char), 23LU, realloc))(#{overlap
large, small, msmall}, '\b', [10280751412894535920, 0,
576460752303423488])

I believe you have to make either opSlice public or add a public
toString.
&quot;Nordlöw&quot; via Digitalmars-d
2014-09-22 19:18:50 UTC
Permalink
On Monday, 15 September 2014 at 02:26:19 UTC, Andrei Alexandrescu
Post by Andrei Alexandrescu via Digitalmars-d
http://dpaste.dzfl.pl/817283c163f5
You implementation seems to hold water at least in my tests and
save memory at

https://github.com/nordlow/justd/blob/master/conceptnet5.d

Thanks :)

I'm however struggling with fast serialization with msgpack. FYI:

https://github.com/msgpack/msgpack-d/issues/43
Loading...