Re: Local static class fields
On Tuesday, 13 August 2019 at 12:22:45 UTC, Simen Kjærås wrote:
On Tuesday, 13 August 2019 at 08:41:02 UTC, Bert wrote:
On Tuesday, 13 August 2019 at 04:43:29 UTC, Paul Backus wrote:
It seems to me like the obvious solution is to use two
different classes, one to store the global state, and one to
store the individual objects in your structure. For example:
class Tree {
State state;
Node root;
}
class Node {
Node[] children;
}
Yes, I forgot to mention this as a solution.
I was going to go in to more detail. This is not a great
solution because it requires a base class simply to hold the
"global" state and it requires nodes to have an accessor(they
won't know which tree they come from).
What you're essentially looking at here is my solution 4):
class Node {
Node parent;
Node[] children;
@property State state() {
return parent.state;
}
}
class Root : Node {
State treeState;
override @property State state() {
return treeState;
}
}
class State {}
What I was thinking though, with D's capabilities, if a
constructor could somehow return a "Voldemort" type that makes
it all work out.
e.g.,
class Tree {
State state;
Node root;
alias root this;
}
then the constructor just returns tree which acts as an node.
It doesn't have to be a voldemort but it at least hides some
of the details...
Ultimately it is not too different from using a dictionary
though, effectively does the same thing.
Something like this may be possible, but it will still need to
keep around a pointer to the context (likely the root), costing
you the exact same as having a pointer to either the root or
the state in each node:
class Root {
State state;
this() { state = new State(); }
auto newNode() {
class Node {
State getState() { return state; }
}
return new Node();
}
}
class State { }
unittest {
auto root1 = new Root();
auto node = root1.newNode();
assert(node.getState() == root1.state);
// Note that Node keeps track of its context, thus taking
up more space:
assert(__traits(classInstanceSize, typeof(node)) >
__traits(classInstanceSize, State));
}
There may be no way around such a problem in that these might
be "optimal". Your's, which added parent in node, might be
better since a dictionary doesn't have to be directly
maintained.
Also, if space is a concern, the dictionary is actually worse
than adding a pointer to the state in each node, as the
internal book-keeping of the dictionary is more than one
pointer's worth per entry (at the very least it needs to keep
both the hash of the Node and the pointer to the state).
I'd like to get away from actually having a different "root"
type though. Mainly because it reduces uniformity and
complicates the design I already have. If I could hide all
these things and it is not too complicated then it would work
better for me.
The solution of having a Root class that derives from Node
causes complications in three situations: When you create a new
tree, when you move a subtree to become a new tree, and when
you move a tree to become a subtree. The last two may or may
not actually occur in your code, but without knowing more, I
have no idea if that's the case. I'm fairly certain you will at
some point be creating new trees, though. If the creation of
new trees is confined to one or two functions while the
creation of new nodes is widespread, this special-casing of
roots should be easily manageable.
However, since you specifically mention in this post that Paul
'added parent in node', you should definitely go with a pointer
to the state in the Node, as per my earlier post. It's faster,
you pay the memory cost anyway, and it's easy for maintainers
(that's you in 6 months cursing your young-and-careless self)
to understand what's going on.
Actually, there's one complication with having a pointer to the
state in each node that we haven't mentioned: is the state
often replaced wholesale? That is, not just its contents
changed, but can the state of a tree suddenly point to a wholly
different instance of the same class? If each node holds a
pointer to it, then this operation is costly. However, this is
generally easy to fix/avoid by a) favor mutation over
reassignment, or b) another layer of indirection.
Generally no, I think that your solution is not great. There is
no reason to contain a pointer in each node. I mentioned in the
other reply that there might be better alternative, a hybrid.
Basically
class StateNode : Node
and then use a limited traversal. Replace every kth node with a
StateNode and simply traverse up to it. One is guaranteed to find
one within kN steps and on average half that. It also then
reduces memory requires by kN.
This seems to be the best all around approach. It still requires
some type of construction but this might be done behind the
scenes by
Re: Local static class fields
On Tuesday, 13 August 2019 at 00:17:13 UTC, DanielG wrote: On Monday, 12 August 2019 at 22:48:43 UTC, Bert wrote: I have a recursive class structure(think of a graph or tree) and I need to keep a global state for it, If I'm understanding the problem correctly, it seems like you have a choice to make: either "bloat" the child nodes by the size of a pointer/reference to the shared tree state (4 or 8 bytes), or forego that by traversing the tree (from child to root node) every time you want to access the state. Yes. It's the typical size/speed issue, if, for example, one could somehow use pointer manipulation. If, say, all the nodes could be allocated using special pointer where the first node could be calculated then it would solve both problems optimally(e.g., ptr & 0x/class_size). Of course this is someone rediculous. In my use case the tree is fixed but it might not always be. I was just curious if there was some trick or if's impossible to really make it happen. But if you don't want traversal every time, you're going to have to cache some kind of pointer (or Tree ID in the case of a central dictionary). I suppose if you got down to the nitty-gritty maybe you could use an 8- or 16-bit value for the key ID? (Disclosure: I know absolutely zero about how D lays out classes and structs in memory, this might not save any memory at all) I guess I could wrap some nodes that contain a pointer to the data equally spaced throughout the hierarchy and that will reduce overhead. E.g., The kNth node has a pointer to the state. This reduces the wasted memory by kN and limits the traversal depth to a max of kN. This might be the easiest method that provides the best of both words. Just inherit from Node and cast to check if it contains the info. It would help if you could provide some rough metrics: - How deep you expect each recursive structure to be (from root to deepest leaf node) - How many total nodes you expect to have across all trees (such that adding a single pointer to each instance would be memory-prohibitive) - How often each node will have to access the shared state (such that traversal-every-time would be too slow) That might help in figuring out the best approach. These are all unknown, it is a general solution. Obviously since these are tree's the depth isn't going to be astronomical but they could be quite deep since arrays are technically tree's.
Re: Abstract classes vs interfaces, casting from void*
On Saturday, 10 August 2019 at 08:20:46 UTC, John Colvin wrote:
On Friday, 9 August 2019 at 13:39:53 UTC, Simen Kjærås wrote:
Thanks for the extra detail.
Is there a solid reason to ever use an interface over an
abstract class? (Other than multiple inheritance).
I'm such a noob at anything related to OO.
The way I look at it: an interface is a guarantee. By saying
interface A { void foo()}
class B: A {}
class C: A {}
void bar(A a) {}
you guarantee that every class that implements interface A has a
function foo and
and bar can be called with anything that implements interface A.
This is completely unrelated to inheritance.
An abstract class is an implementation, most likely a base class.
By saying
abstract class A {void foo()}
class B: A {}
class C: B {}
void bar(A a) {}
you express that you want bar to be called with any subclass of A.
e.g. a bitmap button inherits from button which inherits from
abstract class widget and implements the signal/slot interfaces.
Another pattern is design by introspection.
An interface defines what something _is_,
by introspection defines what something _CanDo_.
That's to say: I don't care if foo is actually (or inherits from)
an InputRange as long as it behaves like it.
can DDOC generate files names including the full path ?
For example if the source tree looks like this: source/ foo/ baz.d bar/ baz.d and generating the docs with something like this: dmd -D -Dd=docs foo/baz.d bar/baz.d the output looks like this: docs/ baz.html one baz overwrites the other. I'd like to have something like this: docs/ foo.baz.html bar.baz.html There's the -op flag, but that litters the source tree with html files. Neither the docs https://dlang.org/spec/ddoc.html nor google provided any insight. Also there's more annoying behavior: - Documentation generation fails if -version s are not provided resulting in a rather long command and it's tedious to manually keep track of it. Is there a way to make it only honor version(none) and treat all other -version s as a given ? - if the -o- isn't provided, dmd complains about missing symbols. Why ? -D enables documentation mode, doesn't it?
error : outer function context of `D main` is needed to `new` nested class `main.main.X`
void main()
{
class X { ... }
auto f = foo!X;
}
then in another module I have a templated function foo that
simply new's x:
auto foo(T)() { return new T; }
yet I get the error.
I realize that X is local to main and I realize I could do
something like
foo(new X);
but that completely defeats the purpose(my context is more
complicated). I need to construct X, not have the user do it.
I thought the templated function would be instantiated at the
call site?
I've tried to "hack" it in various ways but nothing works. I've
imported the model, but since X is local to main it can't be
seen. I've tried to fully qualify it but it can't be found.
main.main.X says something about void(the return type of main()):
no property `` for type `void`.
template foo(T)
{
alias foo = T;
alias foo = () { return new T; }; // or
}
then I can do new foo!T, but I cannot actually construct T like I
need to. I cannot seem to return a proper type either. I've tried
returning a lambda and so on, but D is enforcing the type be
accessible even if the function will be used in the correct
context.
I don't understand stand why it is a problem when the template
functions are suppose to be instantiated at the call site.
Seems like a complete pain just to be able to construct a type
outside it's context(but the construction is totally within the
context, or should be. I'm simply trying to provide a simple
wrapper that does some boilerplate and makes everything look
nice).
Re: error : outer function context of `D main` is needed to `new` nested class `main.main.X`
On Thursday, 15 August 2019 at 01:55:17 UTC, Bert wrote:
void main()
{
class X { ... }
I would just make it `static class X` and then it shoudl work
fine.
Won't be able to access main's local variables then though, but
you could pass the necessary ones through the constructors or
something.
Re: Is it possible to target all platforms that Qt Quick can target?
I cannot use QML for D or other D Qt libraries. I'm writing something important and need all of Qt Creator and its C++ editing environment. I don't wish to go through the bad experience of using those libraries. I've tried it before. I do D in Visual D, and that would be for the backend only, connected to the GUI code using a dynamic library. I will assume the answer is no, D is not support that yet (targeting all platforms with a dynamic library, all platforms that Qt Quick supports).
Re: Desktop app with vibe.d
On Monday, 12 August 2019 at 10:41:57 UTC, GreatSam4sure wrote: Pls I want to know if it is possible to build desktop app with vibe.d just like nodejs. I am not satisfy with the GUI of Dlang such as dlangui and gtkd. I don't think they have good styling capabilities like HTML and CSS. I will be happy if I can build an app in D with fanciful ui. I will also be happy if you know any other way to build a fanciful ui in D like adobe flex, javafx, etc. Kai Nacke has a chapter (it's chapter 8) in his book "D Web Development / Packt Publishing"
Re: How should I sort a doubly linked list the D way?
On Tuesday, 13 August 2019 at 18:28:35 UTC, Ali Çehreli wrote: On 08/13/2019 10:33 AM, Mirjam Akkersdijk wrote: > On Tuesday, 13 August 2019 at 14:04:45 UTC, Sebastiaan Koppe wrote: >> Convert the nodes into an D array, sort the array with nodes.sort!"a.x >> < b.x" and then iterate the array and repair the next/prev pointers. If possible, I would go further and ditch the linked list altogether: Just append the nodes to an array and then sort the array. It has been shown in research, conference presentations, and in personal code to be the fasted option is most (or all) cases. > doesn't the nature of the dynamic array slow it down a bit? Default bounds checking is going to cost a tiny bit, which you can turn off after development with a compiler flag. (I still wouldn't.) The only other option that would be faster is an array that's sitting on the stack, created with alloca. But it's only for cases where the thread will not run out of stack space and the result of the array is not going to be used. > can't I define an array of fixed size, which is dependent on the input > of the function? arr.length = number_of_elements; All elements will be initialized to the element's default value, which happens to be null for pointers. (If we are back to linked list Node pointers.) However, I wouldn't bother with setting length either as the cost of automatic array resizing is amortized, meaning that it won't hurt the O(1) algorithmic complexity in the general case. In the GC case that D uses, it will be even better: because if the GC knowns that the neighboring memory block is free, it will just add that to the dynamic array's capacity without moving elements to the new location. Summary: Ditch the linked list and put the elements into an array. :) There are mainly three reasons why arrays are nowadays faster than double linked lists: - pointer chasing can difficultly be paralized and defeats prefetching. Each pointer load may cost the full latency to memory (hundreds of cycles). In a multiprocessor machine may also trigger a lot of coherency trafic. - on 64 bit systems 2 pointers cost 16 bytes. If the payload is small, there is more memory used in the pointer than in the data. - when looping in an array the OO machinery will be able to parallelize execution beyond loop limits. - reduced allocation, i.e. allocation is done in bulk => faster GC for D. It is only when there are a lot of external references to the payload in the list that using an array may become too unwieldy, i.e. if moving an element in memory requires the update of other pointers outside of the list.
Re: How should I sort a doubly linked list the D way?
On 08/13/2019 03:12 PM, Mirjam Akkersdijk wrote: > For the application I am writing, it makes very much sense to use a DLL. Yes, Dynamically Linked Libraries can be useful. Oh wait... You mean Doubly-Linked List. :o) > I tried setting the length first and iterating through it with `nodes[i] > = ...` As Mike Parker said, it should be .reserve. > and the implementation did not run noticeably faster (10 trials), That's the most important part: You profiled and it was the same. (Although, profiling is tricky business as well; it can be difficult to measure the operation that you are interested in.) The performance will depend on many factors: * First, if there aren't many number of nodes it shouldn't matter. (That's why I would choose the simpler arrays.) * Doubly-linked list nodes will have two extra pointers per element. As a general rule, larger the data slower the data structure. * Pointer chasing through 'next' pointers will make the program jump around in memory. This will be slower compared to consecutive elements that arrays provide. But if processing the elements cause pointer chasing anyway, then it shouldn't matter much. Another topic to read and watch is "data oriented programming". This talk by Mike Acton is eye opening: https://www.youtube.com/watch?v=rX0ItVEVjHc * Is data appended and removed throughout the life of the program or are the nodes set once in the beginning and then only used? * Are elements accessed randomly or always in sequence. (If the latter, modern CPUs promise that arrays will be better.) * etc. Ali
Re: string to ubyte[]
On Wednesday, 14 August 2019 at 15:11:44 UTC, berni wrote: The reason is, that this expression creates a string and not a ubyte[]... it should be ok to just cast it in this case.
string to ubyte[]
I've got a function which takes two strings and should return
them as a ubyte[] with additional zero bytes in between and
around. This works:
ubyte[] convert_string_pair(string first, string second)
{
auto b = new ubyte[](0);
b ~= 0x00 ~ first ~ 0x00 ~ second ~ 0x00;
return b;
}
But I think it would be more elegant to do it in a single return
statement, but unfortunately this does not work:
ubyte[] convert_string_pair(string first, string second)
{
return 0x00 ~ first ~ 0x00 ~ second ~ 0x00;
}
The reason is, that this expression creates a string and not a
ubyte[]...
Re: string to ubyte[]
On Wed, Aug 14, 2019 at 03:11:44PM +, berni via Digitalmars-d-learn wrote:
[...]
> but unfortunately this does not work:
>
> >ubyte[] convert_string_pair(string first, string second)
> >{
> >return 0x00 ~ first ~ 0x00 ~ second ~ 0x00;
> >}
>
> The reason is, that this expression creates a string and not a
> ubyte[]...
Try:
ubyte[] convert_string_pair(string first, string second)
{
return cast(ubyte[])(0x00 ~ first ~ 0x00 ~ second ~ 0x00);
}
T
--
What did the alien say to Schubert? "Take me to your lieder."
