Re: How should I sort a doubly linked list the D way?
On Tuesday, 13 August 2019 at 22:12:23 UTC, Mirjam Akkersdijk
wrote:
Though, it left me with some semi-offtopic questions unanswered:
(1) Ali, do you mean that from an optimization viewpoint, it's
better to keep appending like `nodes ~= ...` instead of setting
the length first? I would like to have some more background on
that claim.
He's not saying it will be better, but that the cost will be
negligible. On every append, the GC allocates new memory only if
the current capacity == 0. When it does allocate, it allocates
more space than it actually needs based on the current length of
the array, so you don't actually have an allocation on every
append. Also, when the adjacent memory block is free and can hold
the additional elements, the allocation consists of extending the
array's memory block and no copying is performed, making the cost
of the allocation even cheaper than it could be.
Anyway, you can use `reserve` when appending rather than setting
the length. This will allocate enough memory without
default-initializing anything and you don't have to worry about
bounds checking.
int[] ints;
ints.reserve(100);
foreach(i; 0..100) {
ints ~= i;
}
See Steve Schveighoffer's array article for details:
https://dlang.org/articles/d-array-article.html
Re: How should I sort a doubly linked list the D way?
On Tuesday, 13 August 2019 at 21:11:41 UTC, H. S. Teoh wrote: A contiguous allocator doesn't help after the list has undergone a large number of insertions/deletions, because of fragmentation. Fragmentation should not be an issue, I insist on keep using a DLL for the base structure in my application and create an array just for sorting operations. No new nodes are added and no nodes are permanently removed. You can still get a cache-efficient linked list by chunking. [...] I very much appreciate this thought, as I was thinking of adding such kind of cache to my implementation. It's still in the early stages and I have yet to see when this would make a considerable impact. I will remember this.
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:
> 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.
For the application I am writing, it makes very much sense to use
a DLL. The approach I am using right now is to: (as stated in the
first post)
void bsort(DLL* list) {
Node*[] nodes;
foreach (i; 0 .. list.size)
nodes ~= get_node(list, i);
nodes.sort!("a.x < b.x");
// (unrelated data structure cleaning up goes here)
}
My concern was that using a dynamic array, continuously appending
to it despite known size, would greatly impact overall
performance. My goal is to make this operation as fast as
possible, the D way.
I tried setting the length first and iterating through it with
`nodes[i] = ...` and the implementation did not run noticeably
faster (10 trials), per Teoh's advice to test out the difference.
For now, I consider this a success and would like to thank
everyone in the thread for assistance and valuable insights.
Though, it left me with some semi-offtopic questions unanswered:
(1) Ali, do you mean that from an optimization viewpoint, it's
better to keep appending like `nodes ~= ...` instead of setting
the length first? I would like to have some more background on
that claim.
(2) I watched the talk and read the paper [1] to be sure. Many
contributors to this thread claim (C++) vectors are nearly always
the preferred choice compared to DLLs, but how come they are much
faster compared to DLLs, given they have nearly the same
functionality?
(3) And I sense this is very closely related to what Ali is on?
[1] http://www.stroustrup.com/Software-for-infrastructure.pdf
Re: How should I sort a doubly linked list the D way?
On Tue, Aug 13, 2019 at 08:42:37PM +, Max Haughton via Digitalmars-d-learn wrote: > On Tuesday, 13 August 2019 at 18:54:58 UTC, H. S. Teoh wrote: [...] > > These days, with CPU multi-level caches and memory access > > predictors, in-place arrays are often the best option for > > performance, up to a certain size. In general, avoid indirection > > where possible, in order to avoid defeating the memory access > > predictor and reduce the number of cache misses. [...] > I saw a Bjarne Stroustrup talk where he benchmarked that the for n > > 1, std::vector was a lot faster than a linked list for all supported > operations. I don't know how clever the caching strategies are on a > modern processor (Pointer chasing), but to my knowledge the only way > of getting a cache efficient linked list would be to effectively have > a very contiguous allocator (Which obviously defeats the purpose of > using a list in the first place) > > Found it: https://www.youtube.com/watch?v=YQs6IC-vgmo A contiguous allocator doesn't help after the list has undergone a large number of insertions/deletions, because of fragmentation. You can still get a cache-efficient linked list by chunking. I.e., instead of a linked-list of individual elements, group the elements into blocks (arrays) that are then linked into a linked list. Then you can still insert/delete elements with sub-O(1) complexity by updating only the affected block, and only occasionally you need to delete a block or allocate a new block. As long as the block size is suitably-sized, it will be cache-coherent most of the time and enjoy the associated performance boosts from the cache hierarchy. For small lists, it will be equivalent to using a single array. For very large lists, you'll also reap the cheap insert/delete flexibility of a linked list. To minimize space wastage from unused slots in the blocks, you could have a list rebalancing based on some desired utilization factor (e.g., if <50% of a block is used, redistribute elements among adjacent blocks). Redistribution should be pretty cache-coherent (except perhaps for some corner cases), because it mostly involves linear copying of elements from one block to another. T -- I am not young enough to know everything. -- Oscar Wilde
Re: How should I sort a doubly linked list the D way?
On Tuesday, 13 August 2019 at 18:54:58 UTC, H. S. Teoh wrote: On Tue, Aug 13, 2019 at 11:28:35AM -0700, Ali Çehreli via Digitalmars-d-learn wrote: [...] Summary: Ditch the linked list and put the elements into an array. :) [...] +1. The linked list may have been faster 20 years ago, before the advent of modern CPUs with caching hierarchies and memory access predictors. These days, with CPU multi-level caches and memory access predictors, in-place arrays are often the best option for performance, up to a certain size. In general, avoid indirection where possible, in order to avoid defeating the memory access predictor and reduce the number of cache misses. T I saw a Bjarne Stroustrup talk where he benchmarked that the for n > 1, std::vector was a lot faster than a linked list for all supported operations. I don't know how clever the caching strategies are on a modern processor (Pointer chasing), but to my knowledge the only way of getting a cache efficient linked list would be to effectively have a very contiguous allocator (Which obviously defeats the purpose of using a list in the first place) Found it: https://www.youtube.com/watch?v=YQs6IC-vgmo
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 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. Yeah, very likely. Although in this case there already is an array; it's going to be close :)
Re: How should I sort a doubly linked list the D way?
On Tue, Aug 13, 2019 at 11:28:35AM -0700, Ali Çehreli via Digitalmars-d-learn wrote: [...] > Summary: Ditch the linked list and put the elements into an array. :) [...] +1. The linked list may have been faster 20 years ago, before the advent of modern CPUs with caching hierarchies and memory access predictors. These days, with CPU multi-level caches and memory access predictors, in-place arrays are often the best option for performance, up to a certain size. In general, avoid indirection where possible, in order to avoid defeating the memory access predictor and reduce the number of cache misses. T -- "If you're arguing, you're losing." -- Mike Thomas
Re: How should I sort a doubly linked list the D way?
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. :) Ali
Re: How should I sort a doubly linked list the D way?
On Tue, Aug 13, 2019 at 12:12:28PM -0600, Jonathan M Davis via Digitalmars-d-learn wrote: > On Tuesday, August 13, 2019 11:33:10 AM MDT Mirjam Akkersdijk via > Digitalmars-d-learn wrote: [...] > > Thank you, this is what I eventually chose to do. It's also fairly > > fast, though doesn't the nature of the dynamic array slow it down a > > bit? Since I already know the size of the array (but just not at > > compile time), can't I define an array of fixed size, which is > > dependent on the input of the function? > > In D, static arrays must know their length at compile time. Dynamic > arrays can have their length determined at runtime. I don't know why a > dynamic array would slow anything down here though - especially if you > just allocate it with the correct length. [...] When it comes down to fine points concerning performance like here, my default response is: are you sure this is an *actual* performance hit? Did you run a profiler to measure the actual runtimes? Static arrays have the advantage that the size is known at compile-time, so the compiler can generate better code (by hard-coding the length, optimizing the memory layout, etc.). But when you pass static arrays around, you have to either slice them, in which case they become identical to dynamic arrays anyway, or pass them on the stack, which in some cases can actually slow things down (you have to copy a potentially large amount of data to/from the stack when passing arguments to a function). Passing a dynamic array (or a slice of a static array) is very fast: it's just a pointer + size pair. Dynamic arrays could potentially incur performance hits if you're appending to them (may need a GC allocation). Static arrays don't have this problem -- but then you can't append to a static array at all. :-P Anyway, splitting hairs over whether to use static arrays or dynamic arrays sounds like premature optimization to me. Before worrying about potential performance problems with using dynamic arrays, always use a profiler to see if the bottleneck is actually in that part of the code. Otherwise it's just a waste of time and energy to "optimize" the code when it isn't even anywhere near the real bottleneck(s) in the program. Profile, profile, profile. Until then, don't sweat it over optimization. T -- Mediocrity has been pushed to extremes.
Re: How should I sort a doubly linked list the D way?
Am 13.08.19 um 11:48 schrieb Mirjam Akkersdijk:
> Hello there,
> If I had a DLL, how would I sort it judging by the node contents, the D
> way?
>
> In C if I were to sort a piece of malloc'd memory pointing to node
> pointers, I would write my compare function and let qsort sort it out.
> In D, I tried to use std.algorithm's sort functionality to no avail,
> because my guess would be it only operates on arrays. This opens up
> another can of worms as I am not fond of VLAs and D desperately wants to
> know what the size is at compile time.
>
> Let's say we this trivial implementation:
>
> Node* get_node(DLL* list, uint index);
>
> struct Node {
> int x;
> Node* prev, next;
> };
>
> struct DLL {
> Node* head;
> uint size;
> };
>
> Node** nodes = cast(Node**) malloc(DLL.size * (Node*).sizeof);
>
> and I would like to sort based on Node.t, how should I tackle it,
> preferably without resorting to C libraries?
I'd do something along the lines of this:
```
import std;
struct Node(T)
{
private:
typeof(this)* prev, next;
public:
T data;
}
struct DoublyLinkedList(T)
{
private:
Node!T* head = null;
Node!T* tail = null;
public:
void pushFront(T t)
{
auto n = new Node!T;
if (head != null)
{
head.prev = n;
}
else
{
tail = n;
}
n.data = t;
n.next = head;
head = n;
}
T front() const @property
{
return head.data;
}
void popFront()
{
head = head.next;
if (head != null)
{
head.prev = null;
}
else
{
tail = null;
}
}
void pushBack(T t)
{
auto n = new Node!T;
if (tail != null)
{
tail.next = n;
}
else
{
head = n;
}
n.data = t;
n.prev = tail;
tail = n;
}
T back() const @property
{
return tail.data;
}
void popBack()
{
tail = tail.prev;
if (tail != null)
{
tail.next = null;
}
else
{
head = null;
}
}
size_t empty() const @property
{
return head == null;
}
auto nodes() @property
{
static struct NodePointerRange
{
private:
Node!T* head;
public:
Node!T* front() @property
{
return head;
}
void popFront()
{
head = head.next;
}
bool empty() const @property
{
return head == null;
}
}
return NodePointerRange(head);
}
}
auto doublyLinkedList(R)(R r) if (isInputRange!R)
{
DoublyLinkedList!(ElementType!R) list;
foreach (e; r)
{
list.pushBack(e);
}
return list;
}
auto doublyLinkedListFromNodePointerRange(R)(R r)
if (isInputRange!R && isPointer!(ElementType!R)
&& isInstanceOf!(Node, PointerTarget!(ElementType!R)))
{
DoublyLinkedList!(TemplateArgsOf!(PointerTarget!(ElementType!R))) list;
foreach (n; r)
{
n.prev = list.tail;
if (list.tail != null)
{
list.tail.next = n;
}
else
{
list.head = n;
}
list.tail = n;
}
list.tail.next = null;
return list;
}
void main()
{
auto list = doublyLinkedList([5, 3, 7, 24, 1]);
// looks natural but allocates new nodes
auto sortedList = list.array.sort.doublyLinkedList;
sortedList.each!writeln;
writeln;
auto anotherList = doublyLinkedList([54, 23, 8]);
// looks a bit uglier but reuses the already allocated nodes
auto anotherSortedList = anotherList.nodes
.array
.sort!((n1, n2) => n1.data < n2.data)
.doublyLinkedListFromNodePointerRange;
anotherSortedList.each!writeln;
}
```
Modulo bugs of course ;)
This uses the GC. If you want to avoid it in favor of malloc (or
std.experimental.allocator), you need to add `free`s (and possibly
referece counting) accordingly.
Re: How should I sort a doubly linked list the D way?
On Tuesday, August 13, 2019 11:33:10 AM MDT Mirjam Akkersdijk via
Digitalmars-d-learn wrote:
> On Tuesday, 13 August 2019 at 14:04:45 UTC, Sebastiaan Koppe
>
> wrote:
> > On Tuesday, 13 August 2019 at 09:48:52 UTC, Mirjam Akkersdijk
> >
> > wrote:
> >> and I would like to sort based on Node.t, how should I tackle
> >> it, preferably without resorting to C libraries?
> >
> > 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.
>
> Thank you, this is what I eventually chose to do. It's also
> fairly fast, though doesn't the nature of the dynamic array slow
> it down a bit? Since I already know the size of the array (but
> just not at compile time), can't I define an array of fixed size,
> which is dependent on the input of the function?
In D, static arrays must know their length at compile time. Dynamic arrays
can have their length determined at runtime. I don't know why a dynamic
array would slow anything down here though - especially if you just allocate
it with the correct length. Appending each element individually instead of
allocating the full dynamic array and then setting each element would
certainly be slower, but once the dynamic array is fully allocated, as far
as accessing elements go, accessing a dynamic array and static array should
be basically the same. The only real difference is that one would have its
elements on the stack, whereas the other would have them on the heap. Even
if you used a static array, you'd have to slice it to pass to sort, which
would mean that you'd be passing it a dynamic array. A dynamic array is
basically just a struct with a pointer and a length. e.g.
struct DynamicArray(T)
{
size_t length;
T* ptr;
}
and accessing its elements is the same as you'd get with a pointer in C
except for the fact that in @safe code, the bounds are checked when indexing
elements. The only thing about dynamic arrays that can get slow is if you're
doing a lot of appending to them, because then it has to keep checking to
see whether it can expand in place or has to allocate a new block of memory
and copy the elements. In that respect, it's similar to C++'s std::vector.
- Jonathan M Davis
Re: How should I sort a doubly linked list the D way?
On Tuesday, 13 August 2019 at 14:04:45 UTC, Sebastiaan Koppe wrote: On Tuesday, 13 August 2019 at 09:48:52 UTC, Mirjam Akkersdijk wrote: and I would like to sort based on Node.t, how should I tackle it, preferably without resorting to C libraries? 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. Thank you, this is what I eventually chose to do. It's also fairly fast, though doesn't the nature of the dynamic array slow it down a bit? Since I already know the size of the array (but just not at compile time), can't I define an array of fixed size, which is dependent on the input of the function?
Re: How should I sort a doubly linked list the D way?
On Tuesday, 13 August 2019 at 12:34:46 UTC, bachmeier wrote: I'm confused by this statement. Are you referring to the qsort in C's stdlib? I had never heard of using that to sort a linked list, so I searched, and it is not possible. Ah yes, maybe I should have elaborated. In C, you can just create an array (1) struct Node* nodes[buf_size]; and then loop over it, filling it with (2) nodes[i] = (DLLbuf + i * sizeof(struct Node)); subsequently calling our dear friend from stdlib (3) qsort(nodes, buf_size, sizeof(struct Node*), buf_compare_function); You can then rechain all nodes together but that's a bit out of scope for this thread unless you do really want me to work it out :) But I was looking for a more D-specific approach to solve this, as it feels archaic to do it the C way. If there is anyone with a better one please let me know.
Re: How should I sort a doubly linked list the D way?
On Tuesday, 13 August 2019 at 09:48:52 UTC, Mirjam Akkersdijk wrote: and I would like to sort based on Node.t, how should I tackle it, preferably without resorting to C libraries? 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.
Re: How should I sort a doubly linked list the D way?
On Tuesday, 13 August 2019 at 09:48:52 UTC, Mirjam Akkersdijk wrote: I would write my compare function and let qsort sort it out. I'm confused by this statement. Are you referring to the qsort in C's stdlib? I had never heard of using that to sort a linked list, so I searched, and it is not possible. https://cboard.cprogramming.com/c-programming/64520-sorting-linked-list-qsort.html https://stackoverflow.com/questions/7091685/doesnt-qsort-c-library-function-work-on-linked-lists: "qsort works on plain arrays of equally sized data, not linked lists"
Re: Local static class fields
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.
--
Simen
Re: How should I sort a doubly linked list the D way?
On Tuesday, 13 August 2019 at 09:48:52 UTC, Mirjam Akkersdijk wrote: Hello there, If I had a DLL, how would I sort it judging by the node contents, the D way? In C if I were to sort a piece of malloc'd memory pointing to node pointers, I would write my compare function and let qsort sort it out. In D, I tried to use std.algorithm's sort functionality to no avail, because my guess would be it only operates on arrays. This opens up another can of worms as I am not fond of VLAs and D desperately wants to know what the size is at compile time. You can check std.container.rbtree which will build sorted "list" for you on every Node insert. Again, not sure how this can be done at compile time.
Re: How should I sort a doubly linked list the D way?
On Tuesday, August 13, 2019 3:48:52 AM MDT Mirjam Akkersdijk via
Digitalmars-d-learn wrote:
> Hello there,
> If I had a DLL, how would I sort it judging by the node contents,
> the D way?
>
> In C if I were to sort a piece of malloc'd memory pointing to
> node pointers, I would write my compare function and let qsort
> sort it out. In D, I tried to use std.algorithm's sort
> functionality to no avail, because my guess would be it only
> operates on arrays. This opens up another can of worms as I am
> not fond of VLAs and D desperately wants to know what the size is
> at compile time.
>
> Let's say we this trivial implementation:
>
> Node* get_node(DLL* list, uint index);
>
> struct Node {
>int x;
>Node* prev, next;
> };
>
> struct DLL {
>Node* head;
>uint size;
> };
>
> Node** nodes = cast(Node**) malloc(DLL.size * (Node*).sizeof);
>
> and I would like to sort based on Node.t, how should I tackle it,
> preferably without resorting to C libraries?
std.algorithm.sort operates on random-access ranges, not just dynamic
arrays, and there's no need to know the size at compile time. I don't know
why you would think that arrays would need to know their size at compile
time unless you've only been using static arrays. However, a doubly-linked
list definitely isn't random access, so it wouldn't work with
std.algorithm.sort, and I don't think that Phobos has anything which would
be able to sort it. There might be a solution somewhere on code.dlang.org,
but I don't know of any that I could point you to. Either way, if there's a
solution floating around that you can use to sort a doubly-linked list in
place, it's not an official one.
- Jonathan M Davis
Re: How should I sort a doubly linked list the D way?
You can make an array from it On Tue, Aug 13, 2019 at 12:05 PM Mirjam Akkersdijk via Digitalmars-d-learn wrote: > > On Tuesday, 13 August 2019 at 09:48:52 UTC, Mirjam Akkersdijk > wrote: > > Hello there, > > If I had a DLL, how would I sort it judging by the node > > contents, the D way? > > > > [...] > > >Node.t > > Node.x, my bad
Re: Desktop app with vibe.d
On Tuesday, 13 August 2019 at 09:44:59 UTC, Russel Winder wrote: On Mon, 2019-08-12 at 20:01 +, DanielG via Digitalmars-d-learn wrote: [...] GtkD allows for "reactive" UI. https://www.reactivemanifesto.org/ There is also Qt, I haven't tried any of the D bindings to Qt, but given Qt is event loop based I am sure it allows for "reactive" UI as well – it definitely does using Python/PySIDE2. GTK+ doesn't have the equivalent of the stage/engine of QML. QML is Qt's version of JavaFX, so you do not need a browser to get a dynamic reactive UI. I want my back end to be in D. I want to write the app in D. I am comfortable with JavaFX, adobe flex and Kotlin, c# to some extent
Re: How should I sort a doubly linked list the D way?
On Tuesday, 13 August 2019 at 09:48:52 UTC, Mirjam Akkersdijk wrote: Hello there, If I had a DLL, how would I sort it judging by the node contents, the D way? [...] Node.t Node.x, my bad
How should I sort a doubly linked list the D way?
Hello there,
If I had a DLL, how would I sort it judging by the node contents,
the D way?
In C if I were to sort a piece of malloc'd memory pointing to
node pointers, I would write my compare function and let qsort
sort it out. In D, I tried to use std.algorithm's sort
functionality to no avail, because my guess would be it only
operates on arrays. This opens up another can of worms as I am
not fond of VLAs and D desperately wants to know what the size is
at compile time.
Let's say we this trivial implementation:
Node* get_node(DLL* list, uint index);
struct Node {
int x;
Node* prev, next;
};
struct DLL {
Node* head;
uint size;
};
Node** nodes = cast(Node**) malloc(DLL.size * (Node*).sizeof);
and I would like to sort based on Node.t, how should I tackle it,
preferably without resorting to C libraries?
Re: Is it possible to target all platforms that Qt Quick can target?
On Mon, 2019-08-12 at 17:45 +, Enjoys Math via Digitalmars-d-learn wrote: > Hi, > > I'm writing my GUI in C++ & Qt Quick. I know that I could > connect to D from the GUI code using a DLL, but can something > similar be done on the other PC OS's and the mobile OS's? > > Thanks. > Looking at https://wiki.dlang.org/GUI_Libraries there are some wrappers to Qt for D, including dqml. I think some may not be as maintained as it would be nice to have. Actually it would be nice if there was one standard D wrapper for Qt and QML as there is GtkD the one true D wrapper to GTK+. -- Russel. === Dr Russel Winder t: +44 20 7585 2200 41 Buckmaster Roadm: +44 7770 465 077 London SW11 1EN, UK w: www.russel.org.uk signature.asc Description: This is a digitally signed message part
Re: Desktop app with vibe.d
On Mon, 2019-08-12 at 20:01 +, DanielG via Digitalmars-d-learn wrote: > On Monday, 12 August 2019 at 10:41:57 UTC, GreatSam4sure wrote: > > 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. > > I haven't seen anybody doing it yet, but in theory you could > launch a browser / Electron instance / etc, and have it connect > via gRPC to code written in D. > > Then you could have a fancy React UI and use D to do the heavy > lifting. GtkD allows for "reactive" UI. https://www.reactivemanifesto.org/ There is also Qt, I haven't tried any of the D bindings to Qt, but given Qt is event loop based I am sure it allows for "reactive" UI as well – it definitely does using Python/PySIDE2. GTK+ doesn't have the equivalent of the stage/engine of QML. QML is Qt's version of JavaFX, so you do not need a browser to get a dynamic reactive UI. -- Russel. === Dr Russel Winder t: +44 20 7585 2200 41 Buckmaster Roadm: +44 7770 465 077 London SW11 1EN, UK w: www.russel.org.uk signature.asc Description: This is a digitally signed message part
Re: What the abstrac final class mean?
On Tuesday, August 13, 2019 3:03:49 AM MDT Jacob Carlborg via Digitalmars-d-
learn wrote:
> On 2019-08-12 11:25, a11e99z wrote:
> > its weird that next compiles in some weird form
> >
> > import std;
> > static class A {
> >
> > static a() { "a".writeln; } // forgot return type
> >
> > }
>
> Since you have specified an attribute on "a", the compiler can infer the
> return type. In this case it's inferred to "void" since there is no
> return statement.
>
> It's not really the attribute that makes it possible for the compiler to
> infer the return type, it probably can in most of the cases. It just
> needs to be an attribute to satisfy the parser.
Indeed. Basically, the compiler needs _something_ there which goes with a
function to make it happy. The same goes with variable declarations. Many
people mistakenly think that auto tells the compiler to infer the type when
in reality all it does is provide a placeholder to make the parser happy.
The type is _always_ inferred unless it's explicitly given, which is why
stuff such as enum, const, or ref can be used by themselves without
specifying the full type. However, because _something_ has to be there to
indicate that it's a declaration, auto is in the language so that the
programmer has a way to indicate that it's a variable or function
declaration. static by itself is plenty to indicate that a declaration is
being provided. auto or void could be used, but they're not necessary.
- Jonathan M Davis
Re: What the abstrac final class mean?
On 2019-08-12 11:25, a11e99z wrote:
its weird that next compiles in some weird form
import std;
static class A {
static a() { "a".writeln; } // forgot return type
}
Since you have specified an attribute on "a", the compiler can infer the
return type. In this case it's inferred to "void" since there is no
return statement.
It's not really the attribute that makes it possible for the compiler to
infer the return type, it probably can in most of the cases. It just
needs to be an attribute to satisfy the parser.
--
/Jacob Carlborg
Blog Post #0061: Cairo Toy Text
When all you want is quick-n-dirty text in a GTK DrawingArea and Pango seems like more than you wanna deal with, Cairo's Toy Text will do the job nicely. Here's how: https://gtkdcoding.com/2019/08/13/0061-cairo-v-toy-text-image-formats.html
How to use #pragma omp parallel for collapse(n) in dlang?
How to use #pragma omp parallel for collapse(n) in dlang?
Re: Local static class fields
On Tuesday, 13 August 2019 at 04:43:29 UTC, Paul Backus wrote:
On Monday, 12 August 2019 at 22:48:43 UTC, Bert wrote:
Making a field static is effectively a global variable to the
class.
I have a recursive class structure(think of a graph or tree)
and I need to keep a global state for it, but this state
actually needs to be different for each tree object. The
reason for this is that structurally it will not change per
tree and if it it is not static then it wastes space
unnecessarily.
[...]
Is there any way to do this more naturally in D?
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 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.
The main issue with your solution is that Nodes themselves do not
have access to the state directly and that is a similar issue
with the dictionary. One has to traverse up to the root and then
get the state, in your case, Tree would have to inherit from Node
so it could be cast and be the root(else the Node would have to
reference the tree).
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.
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.
Re: Local static class fields
On Monday, 12 August 2019 at 22:48:43 UTC, Bert wrote:
Making a field static is effectively a global variable to the
class.
I have a recursive class structure(think of a graph or tree)
and I need to keep a global state for it, but this state
actually needs to be different for each tree object. The reason
for this is that structurally it will not change per tree and
if it it is not static then it wastes space unnecessarily.
class X
{
X[] x;
static State s;
}
making s non-static has the problem that every X will allocate
storage for s wasting space since for any instance chain of X's
they will all have the same s. Making it static though then
makes it the same for all instance chain's of X, of which it
should be local to each.
One way around this is to use an dictionary that associates
each state to each instance chain.
That is there is a initial X that is the parent of the chain
and we can then associate a state to it's address, any other
chain will have a different initial X and so we can get a new
state.
class X
{
X[] x;
static State[X] s;
}
This is not a huge difficulty to do but does require finding
the initial X to use, which is not difficult but wastes cycles
for large chains. There will, of course, be a constructor that
constructs a chain and creates a new state for it and updates s.
Is there any way to do this more naturally in D?
First: Are you low on memory? Is traversing the tree actually
slow? Since you don't know which of these issues to prioritize,
in all likelihood the answer to both questions is no, and you
should use the solution that's easier to read.
Of course, that's not the answer you want to hear. Let's consider
the alternatives:
1) Embed it in each node. Costs 1 pointer's worth of memory per
node. Very fast. Very easy to understand.
2) Use a dictionary with entries for each node. Costs more than 1
pointer's worth of memory per node. Fast, but not quite as fast
as 1). 1) is almost definitely a better option.
3) Use a dictionary with entries for each root node. Costs more
than 1 pointer's worth of memory, but per tree instead of per
node. Requires traversal of the tree to find the root, so slower
than both 1) and 2), especially for deep hierarchies. Complicated
code.
4) Use a derived class for the root node (class RootX : X { State
s }). Still requires traversing the tree to find the root, likely
via a virtual method. Also requires a bit more work setting up
the tree. Might be faster than 3), definitely smallest memory
footprint. Relatively easy to follow.
There may be other options, but from the above I'd go with either
1) or 4).
Now, I've noticed that X doesn't have a pointer to its parent, so
traversing the tree to find the root is currently impossible. If
this is true, and you have no other use for traversing up the
tree, then 1) is the way to go, as 2) is almost never a better
option, and 3) and 4) requires adding a parent pointer so you'll
pay the memory price anyway.
--
Simen
Re: Local static class fields
On Tuesday, 13 August 2019 at 04:43:29 UTC, Paul Backus wrote:
On Monday, 12 August 2019 at 22:48:43 UTC, Bert wrote:
Making a field static is effectively a global variable to the
class.
I have a recursive class structure(think of a graph or tree)
and I need to keep a global state for it, but this state
actually needs to be different for each tree object. The
reason for this is that structurally it will not change per
tree and if it it is not static then it wastes space
unnecessarily.
[...]
Is there any way to do this more naturally in D?
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;
}
So I have a Node. How do I find the Tree it belongs to?
--
Simen
Re: Why is this allowed? Inheritance variable shadowing
On Tuesday, 13 August 2019 at 06:39:24 UTC, a11e99z wrote:
On Tuesday, 13 August 2019 at 05:57:23 UTC, Mike Parker wrote:
On Tuesday, 13 August 2019 at 04:40:53 UTC, Chris Katko wrote:
OT:
and again how to easy to google info about error/warning just
with one word "CS0108"
D can use attrs for such things.
OT:
1) need to add compiler attrs that speaks with compiler - they
are change code generation, compiler passes or something. like
pragmas do.
2) need to separate all attrs in a separate construction like C#
do
[inline, nextOne, returns: someAttrToReturnValue]
int meth( [argAttrCanBeToo] int x ) { }
or
[hide]
public int x = 2;
cuz its visually separated and easy to skip it with eye when u
reading/reviewing code.
it can be mess for now:
pure @trusted int meth( int x ) @nogc nothrow { return 5; }
NB all of this attrs is compiler attrs not user, they changes
compilation.
- no possibility add attr to args or returns
- some attrs with "@" and some don't
- its hard to read when D adds 2-3 attrs more for next 5-10 years
my wishlist of new compilation attrs:
- [hiding] for subj
- [offset(N)] for explicit struct alignment without mess with
unions/align(4) cuz sometimes I know exactly offset for field and
I can point it with no side effects calcs adding pads, unions and
etc
- [inline(bool)] instead of pragma( inline, true ) that looks
like compiler attr but another way
- [deprecated(text)]
- [nodiscard] cannot discard return value
- etc
Re: Why is this allowed? Inheritance variable shadowing
On Tuesday, 13 August 2019 at 05:57:23 UTC, Mike Parker wrote:
On Tuesday, 13 August 2019 at 04:40:53 UTC, Chris Katko wrote:
I don't know if I'd call that shadowing. This is how it works
in Java, too. There's no such thing as a vtable for member
variables -- each class gets its own set and they don't
conflict. The only time it could be really be called shadowing
is when the base class member is protected, as then it's
accessible in the subclass scope.
Also, it's not the same thing as overriding. Overriding means
that when you call base.foo(), you get sub.foo()'s
implementation. But when you access base.var, you get base.var
and not sub.var.
I would find it extremely annoying if it worked the way you're
expecting it to.
C# results:
main.cs(8,14): warning CS0108: `B.x' hides inherited member
`A.x'. Use the new keyword if hiding was intended
main.cs(4,14): (Location of the symbol related to previous
warning)
Compilation succeeded - 1 warning(s)
mono main.exe
1
2
with "new" keyword that is used to hide a method, property,
indexer, or event of the base class into the derived class.
class B : A {
public new int x = 2;
// I tell "I want hiding. Ensure "x exists in parent""
explicitly
// almost same meaning as "override"
}
OT:
and again how to easy to google info about error/warning just
with one word "CS0108"
Re: Why is this allowed? Inheritance variable shadowing
On Tuesday, 13 August 2019 at 04:40:53 UTC, Chris Katko wrote:
You can drop this straight into run.dlang.io:
import std.stdio;
class base{ float x=1;}
class child : base {float x=2;} //shadows base variable!
void main()
{
base []array;
child c = new child;
array ~= c;
writeln(c.x); //=2
writeln(array[0].x); //=1 //uses BASE's interface, yes,
//but why does the CHILD instance one exist at all?
}
It appears to be legal C++ as well but I can't imagine a
situation where you'd want to allow the HUGE risk of
shadowing/aliasing variables in an child class. Why is
inheritance shadowing allowed? Especially when in D you have to
explicitly "override" existing _methods_ but not
fields/variables?
To quote a Stack Overflow comment on C++ having this "It's not
a compile error, but it's certainly a design one." Is this
allowed just because "C++ does it" or because it has some sort
of real world use that justifies the risk?
Personally, I'd love a compile-time warning that I could turn
on that flags this situation.
Thanks for your help,
--Chris
I don't know if I'd call that shadowing. This is how it works in
Java, too. There's no such thing as a vtable for member variables
-- each class gets its own set and they don't conflict. The only
time it could be really be called shadowing is when the base
class member is protected, as then it's accessible in the
subclass scope.
Also, it's not the same thing as overriding. Overriding means
that when you call base.foo(), you get sub.foo()'s
implementation. But when you access base.var, you get base.var
and not sub.var.
I would find it extremely annoying if it worked the way you're
expecting it to.
