Re: FIFO
On Monday, 13 May 2024 at 15:07:39 UTC, Andy Valencia wrote: On Sunday, 12 May 2024 at 22:03:21 UTC, Ferhat Kurtulmuş wrote: https://dlang.org/phobos/std_container_slist.html This is a stack, isn't it? LIFO? Ahh yes. Then use dlist Thank you. I read its source, and was curious so I wrote a small performance measurement: put 10,000 things in a FIFO, pull them back out, and loop around that 10,000 times. My FIFO resulted in: Also try the code I gave in this thread: https://forum.dlang.org/post/fgzvdhkdyevtzznya...@forum.dlang.org In fact, please use this facility in the standard library: https://dlang.org/phobos/std_datetime_stopwatch.html#benchmark SDB@79
Re: FIFO
On Monday, 13 May 2024 at 15:07:39 UTC, Andy Valencia wrote:
On Sunday, 12 May 2024 at 22:03:21 UTC, Ferhat Kurtulmuş wrote:
https://dlang.org/phobos/std_container_slist.html
This is a stack, isn't it? LIFO?
Ahh yes. Then use dlist
Thank you. I read its source, and was curious so I wrote a
small performance measurement: put 10,000 things in a FIFO,
pull them back out, and loop around that 10,000 times. My FIFO
resulted in:
real0m1.589s
user0m1.585s
sys 0m0.004s
And the dlist based one:
real0m4.731s
user0m5.211s
sys 0m0.308s
Representing the FIFO as a linked list clearly has its cost,
but I found the increased system time interesting. OS memory
allocations maybe?
The code is spaghetti, fifo/dlist, but it seemed the easiest
way to see the two API's being used side by side:
version(fifo) {
import tiny.fifo : FIFO;
} else {
import std.container.dlist : DList;
}
const uint ITERS = 10_000;
const uint DEPTH = 10_000;
void
main()
{
version(fifo) {
auto d = FIFO!uint();
} else {
auto d = DList!uint();
}
foreach(_; 0 .. ITERS) {
foreach(x; 0 .. DEPTH) {
version(fifo) {
d.add(x);
} else {
d.insertBack(x);
}
}
foreach(x; 0 .. DEPTH) {
version(fifo) {
assert(x == d.next());
} else {
assert(x == d.front());
d.removeFront();
}
}
}
}
thank you for sharing the results. Everything I read about queues
recommends doublylinked lists. With your array based
implementatio if you are consuming the elements faster than
pushing new elements, your array buffer never resize which is
costly. This should explain why your array based queue is more
performant.
Re: FIFO
On Monday, 13 May 2024 at 15:07:39 UTC, Andy Valencia wrote:
Representing the FIFO as a linked list clearly has its cost,
but I found the increased system time interesting. OS memory
allocations maybe?
I know you want FIFO, I usually keep this on hand for fixed size
LIFO; It can easily convert to FIFO and doesn't use LinkedList:
```d
class LIFO(T)
{
T * element;
size_t length, size;
this(size_t s) {
element = cast(T*)new T[s];
length = s;
}
auto rewind() => size = length;
bool empty() => !size;
auto front() => element[size - 1];
auto popFront() => --size;
auto pop() => empty ? T(0) : element[--size];
alias push = insertFront;
auto insertFront(T value)
in(size < length, "Stack is overflow!")
=> element[size++] = value;
auto ref opDollar() => length;
auto ref opIndex(size_t i) => element[i];
auto ref opSlice(size_t first, size_t last)
=> element[first..last];
} unittest {
enum test = 7;
auto stack = new LIFO!size_t(test);
assert(!stack.size);
foreach (prime; 1..test + 1)
{
stack.insertFront(prime);
}
assert(stack.size == test); // == 7
stack.writeln(": ", stack.length); // [7, 6, 5, 4, 3, 2, 1]: 7
stack[$/2].writeln("-", stack[0]); // 4-1
stack.rewind();
stack.size.write(": ["); // 10:
while (auto next = stack.pop)
{
if (next == 1) next.writeln("]");
else next.write(", ");
}
stack.size.writeln; // 0
stack.rewind();
assert(stack.size == test);
}
SDB@79
Re: FIFO
On Sunday, 12 May 2024 at 22:03:21 UTC, Ferhat Kurtulmuş wrote:
https://dlang.org/phobos/std_container_slist.html
This is a stack, isn't it? LIFO?
Ahh yes. Then use dlist
Thank you. I read its source, and was curious so I wrote a small
performance measurement: put 10,000 things in a FIFO, pull them
back out, and loop around that 10,000 times. My FIFO resulted in:
real0m1.589s
user0m1.585s
sys 0m0.004s
And the dlist based one:
real0m4.731s
user0m5.211s
sys 0m0.308s
Representing the FIFO as a linked list clearly has its cost, but
I found the increased system time interesting. OS memory
allocations maybe?
The code is spaghetti, fifo/dlist, but it seemed the easiest way
to see the two API's being used side by side:
version(fifo) {
import tiny.fifo : FIFO;
} else {
import std.container.dlist : DList;
}
const uint ITERS = 10_000;
const uint DEPTH = 10_000;
void
main()
{
version(fifo) {
auto d = FIFO!uint();
} else {
auto d = DList!uint();
}
foreach(_; 0 .. ITERS) {
foreach(x; 0 .. DEPTH) {
version(fifo) {
d.add(x);
} else {
d.insertBack(x);
}
}
foreach(x; 0 .. DEPTH) {
version(fifo) {
assert(x == d.next());
} else {
assert(x == d.front());
d.removeFront();
}
}
}
}
Re: FIFO
On Saturday, 11 May 2024 at 23:44:28 UTC, Andy Valencia wrote: I need a FIFO for a work scheduler, and nothing suitable jumped out at me. I wrote the following, but as a newbie, would be happy to receive any suggestions or observations. TIA! [...] I don't know your use case, maybe you have a similar problem I had to solve years ago. https://forum.dlang.org/post/xktftztisodpngcow...@forum.dlang.org
Re: FIFO
On Sunday, 12 May 2024 at 21:08:24 UTC, Andy Valencia wrote: On Sunday, 12 May 2024 at 19:45:44 UTC, Ferhat Kurtulmuş wrote: On Saturday, 11 May 2024 at 23:44:28 UTC, Andy Valencia wrote: I need a FIFO for a work scheduler, and nothing suitable jumped out at me. ... https://dlang.org/phobos/std_container_slist.html This is a stack, isn't it? LIFO? Andy Ahh yes. Then use dlist
Re: FIFO
On Sunday, 12 May 2024 at 19:45:44 UTC, Ferhat Kurtulmuş wrote: On Saturday, 11 May 2024 at 23:44:28 UTC, Andy Valencia wrote: I need a FIFO for a work scheduler, and nothing suitable jumped out at me. ... https://dlang.org/phobos/std_container_slist.html This is a stack, isn't it? LIFO? Andy
Re: FIFO
On Saturday, 11 May 2024 at 23:44:28 UTC, Andy Valencia wrote: I need a FIFO for a work scheduler, and nothing suitable jumped out at me. I wrote the following, but as a newbie, would be happy to receive any suggestions or observations. TIA! [...] "next" is not a usual range primitive word in dlang. Why not just using slist.
Re: FIFO
On Saturday, 11 May 2024 at 23:44:28 UTC, Andy Valencia wrote: I need a FIFO for a work scheduler, and nothing suitable jumped out at me. I wrote the following, but as a newbie, would be happy to receive any suggestions or observations. TIA! [...] https://dlang.org/phobos/std_container_slist.html
FIFO
I need a FIFO for a work scheduler, and nothing suitable jumped
out at me. I wrote the following, but as a newbie, would be
happy to receive any suggestions or observations. TIA!
/*
* fifo.d
* FIFO data structure
*/
module tiny.fifo;
import std.exception : enforce;
const uint GROWBY = 16;
/*
* This is a FIFO, with "hd" walking forward and "tl" trailing
* behind:
*tl hd /Add here next
*v v
* | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7
*
* Mildly complicated by a module-size indexing.
*/
struct FIFO(T) {
T[] items;
ulong hd, tl, length;
void
add(T t) {
// Make more room when needed
if (this.items.length == this.length) {
assert(this.hd == this.tl);
// Add room and shuffle current contents
auto olen = this.items.length;
auto newlen = olen + GROWBY;
this.items.length = newlen;
this.tl = (this.tl + GROWBY) % newlen;
// Shuffle what we're butted up against to their
// new position at the top of this.items[]
ulong moved = olen - this.hd;
this.items[$ - moved .. $] =
this.items[this.hd .. this.hd + moved];
}
// Add item at next position
this.items[hd] = t;
this.hd = (this.hd + 1) % this.items.length;
this.length += 1;
}
// Give back next
T
next() {
enforce(this.length > 0, "next() from empty FIFO");
this.length -= 1;
auto res = this.items[this.tl];
this.tl = (this.tl + 1) % this.items.length;
return res;
}
}
unittest {
auto f = FIFO!uint();
f.add(1);
f.add(2);
f.add(3);
assert(f.next() == 1);
assert(f.next() == 2);
assert(f.next() == 3);
assert(f.length == 0);
// Now overflow several times
f = FIFO!uint();
foreach(x; 0 .. GROWBY * 3 + GROWBY/2) {
f.add(x);
}
foreach(x; 0 .. GROWBY * 3 + GROWBY/2) {
assert(f.next() == x);
}
assert(f.length == 0);
}
version(unittest) {
void
main()
{
}
}
Re: To switch GC from FIFO to LIFO paradigm.
On Fri, Jan 15, 2021 at 08:19:18PM +, tsbockman via Digitalmars-d-learn wrote: [...] > However, generational GCs are somewhat closer to LIFO than what we > have now, which does provide some performance gains under common usage > patterns. People have discussed adding a generational GC to D in the > past, and I think the conclusion was that it requires pervasive write > barriers (not the atomics kind), which leadership considers > inappropriate for D for other reasons. Also note that generational GCs are designed to cater to languages like Java or C#, where almost everything is heap-allocated, so you tend to get a lot of short-term allocations that go away after a function call or two and become garbage. In that context, a generational GC makes a lot of sense: most of the garbage is in "young" objects, so putting them in a separate generation from "older" objects helps reduces the number of objects you need to scan. In idiomatic D, however, by-value, stack-allocated types like structs are generally preferred over heap-allocated classes where possible, with the latter tending to be used more for longer-term, more persistent objects. So there's less short-term garbage, and it's unclear how much improvement one might see with a generational GC. It may not make as big of a difference as one might expect because usage patterns differ across languages. (Of course, this assumes idiomatic D... if you write D in Java style with lots of short-lived class objects, a generational GC might indeed make a bigger difference. But you'd lose out on the speed of stack-allocated objects. It's unclear how this compares with modern JVMs with JIT that optimizes away some heap allocations, though.) T -- "I'm running Windows '98." "Yes." "My computer isn't working now." "Yes, you already said that." -- User-Friendly
Re: To switch GC from FIFO to LIFO paradigm.
On Friday, 15 January 2021 at 12:39:30 UTC, MGW wrote: GC cleans memory using the FIFO paradigm. Is it possible to switch GC to work using the LIFO paradigm? As others already said, the current GC isn't FIFO; it just scans everything once in a while a frees whatever it can, new or old. However, generational GCs are somewhat closer to LIFO than what we have now, which does provide some performance gains under common usage patterns. People have discussed adding a generational GC to D in the past, and I think the conclusion was that it requires pervasive write barriers (not the atomics kind), which leadership considers inappropriate for D for other reasons.
Re: To switch GC from FIFO to LIFO paradigm.
On Friday, 15 January 2021 at 12:39:30 UTC, MGW wrote: GC cleans memory using the FIFO paradigm. Is it possible to switch GC to work using the LIFO paradigm? AFAIK the GC just sweeps, and the only queue is for destructors (unreachable memory) iirc
Re: To switch GC from FIFO to LIFO paradigm.
On 1/15/21 7:39 AM, MGW wrote: GC cleans memory using the FIFO paradigm. Is it possible to switch GC to work using the LIFO paradigm? I'm not sure what you mean. I don't think there's any guaranteed order for GC cleanup. -Steve
To switch GC from FIFO to LIFO paradigm.
GC cleans memory using the FIFO paradigm. Is it possible to switch GC to work using the LIFO paradigm?
Re: Non-blocking reads of a fifo (named pipe)?
On Monday, 3 December 2018 at 23:32:10 UTC, Anonymouse wrote: I have a fifo that I want to read lines from, but everything is blocking. [...] How can I go about doing this to get non-blocking reads? Or perhaps a way to test whether there is text waiting in the fifo? File.eof is not it. [...] I did this i think for my AsyncProcess class. It was a while ago and i never used it but IIRC it seemed to work on linux (not on Windows still IIRC) https://github.com/BBasile/iz/blob/master/import/iz/classes.d#L1584
Re: Non-blocking reads of a fifo (named pipe)?
On Mon, Dec 03, 2018 at 11:32:10PM +, Anonymouse via Digitalmars-d-learn
wrote:
> I have a fifo that I want to read lines from, but everything is
> blocking.
>
> execute([ "mkfifo", filename ]);
> File fifo = File(filename, "r"); // blocks already
> immutable input = fifo.readln(); // blocks
> foreach (line; fifo.byLineCopy) { /* blocks */ }
>
> How can I go about doing this to get non-blocking reads? Or perhaps a
> way to test whether there is text waiting in the fifo? File.eof is not
> it.
>
> if (fifo.hasData)
> {
> immutable stuff = fifo.readln();
> // ...
> }
I assume you're using Posix? In which case, you should take a look at
the `select` or `epoll` system calls. Cf. core.sys.posix.sys.select.
Or possibly `fcntl` (search for O_NONBLOCK), or call `open` directly
with O_NONBLOCK.
There's no common cross-platform way to do this, so generally you have
to write your own code to handle it.
T
--
Music critic: "That's an imitation fugue!"
Non-blocking reads of a fifo (named pipe)?
I have a fifo that I want to read lines from, but everything is
blocking.
execute([ "mkfifo", filename ]);
File fifo = File(filename, "r"); // blocks already
immutable input = fifo.readln(); // blocks
foreach (line; fifo.byLineCopy) { /* blocks */ }
How can I go about doing this to get non-blocking reads? Or
perhaps a way to test whether there is text waiting in the fifo?
File.eof is not it.
if (fifo.hasData)
{
immutable stuff = fifo.readln();
// ...
}
Re: Deleting a file with extsion *.FIFO in Windows
On 6/1/2018 12:06 AM, vino.B wrote: On Thursday, 24 May 2018 at 11:31:15 UTC, bauss wrote: On Thursday, 24 May 2018 at 06:59:47 UTC, Vino wrote: Hi All, Request your help on how to delete a file which has the extension .fifo (.javast.fifo) in Windows. From, Vino.B What exactly is your issue with it? Hi Bauss, We have a java program which creates a file with extension .fifo and we have another program written in D to clean up the old file, so the D code is not able to delete these files using any of the D function provided it states "Access Denied" we tried to provide the full access manually even then it is not able to delete such files. From, Vino.B Are the files by chance marked as read only (when you right click on a .fifo file and select properties)?
Re: Deleting a file with extsion *.FIFO in Windows
On Thursday, 24 May 2018 at 11:31:15 UTC, bauss wrote: On Thursday, 24 May 2018 at 06:59:47 UTC, Vino wrote: Hi All, Request your help on how to delete a file which has the extension .fifo (.javast.fifo) in Windows. From, Vino.B What exactly is your issue with it? Hi Bauss, We have a java program which creates a file with extension .fifo and we have another program written in D to clean up the old file, so the D code is not able to delete these files using any of the D function provided it states "Access Denied" we tried to provide the full access manually even then it is not able to delete such files. From, Vino.B
Re: Deleting a file with extsion *.FIFO in Windows
On Thursday, 24 May 2018 at 06:59:47 UTC, Vino wrote: Hi All, Request your help on how to delete a file which has the extension .fifo (.javast.fifo) in Windows. From, Vino.B What exactly is your issue with it?
Deleting a file with extsion *.FIFO in Windows
Hi All, Request your help on how to delete a file which has the extension .fifo (.javast.fifo) in Windows. From, Vino.B
Re: FIFO stack
Am 26.10.2011, 18:00 Uhr, schrieb Dominic Jones dominic.jo...@qmul.ac.uk: Also an plain array is a good stack. :) I'd rather not use a plain array because (I assume) that when I push or pop using arrays, a swap array is created to resize the original. If this is not the case, then an array will certainly do. -Dominic Someone could have told me that the topic wasn't FILO stacks ^^. A FILO stack can use a dynamic array with assumeSafeAppend, which avoids the copy by telling the runtime that I definitely wont overwrite anything valuable in the array when I write pop(); push(...); (There are no other array slices operating on the same data block)
Re: FIFO stack
Dominic Jones wrote: Hello, I was looking for a FIFO stack in std.containers but only found SList and Array which both appear to essentially operate as LIFO stacks. Is there any standard container with which I can push items on to a list, then later pop them off from the bottom of that list? If so, then how? Thank you, Dominic Jones The Array can be used as both LIFO and FIFO structure.
Re: FIFO stack
To conclude the matter regarding the absence of a FIFO stack in the standard library and the not so good alternative of arrays (in particular where there are a significant number of push-pops and the maximum length is not initially known): Does anyone in-the-know know if something like DList (a doubly linked list) will be added to std.containers in the near future? I, for one, would very much appreciate its implementation in the standard library. Regards, Dominic
Re: FIFO stack
Ary Manzana a...@esperanto.org.ar wrote in message news:j89gle$9nn$1...@digitalmars.com... On 10/26/11 1:28 PM, Jonathan M Davis wrote: On Wednesday, October 26, 2011 09:00 Dominic Jones wrote: Also an plain array is a good stack. :) I'd rather not use a plain array because (I assume) that when I push or pop using arrays, a swap array is created to resize the original. If this is not the case, then an array will certainly do. -Dominic Not exactly. If you want to know more about how arrays work, you should read this: http://www.dsource.org/projects/dcollections/wiki/ArrayArticle It's a great read. As for using an array as a stack, you can do it with a wrapper struct, but using it by itself would result in a lot more reallocations than you'd want, as discussed here: https://www.semitwist.com/articles/article/view/don-t-use-arrays-as-stacks - Jonathan M Davis I think that if you have to read an article that long, with all the explanations of the different caveats a programmer can bump to when using them, to understand how arrays and slices work something must be wrong. Things should be simpler. FWIW, my article can be summarized with a line that's [poorly] located right around the middle (annotations added): Slicing an array is fast [no allocation or copying], and appending is usually fast [usually no allocation or copying], but slicing the end off and then appending is slow [does an allocate and copy]. I guess I have a habit of making things longer than they need to be ;)
Re: FIFO stack
Dominic Jones dominic.jo...@qmul.ac.uk wrote in message news:j89arh$2ua3$1...@digitalmars.com... Also an plain array is a good stack. :) I'd rather not use a plain array because (I assume) that when I push or pop using arrays, a swap array is created to resize the original. If this is not the case, then an array will certainly do. -Dominic The matter of using D's arrays as a LIFO is discussed the other branch of this thread (ie, you can do it, but it's slow because a pop then push will reallocate and copy), but as far as a FIFO: That may actually be reasonable to do as an array: Decreasing the length of an array (from either end) is a trivial matter that never allocates or copies. Appending to the end *usually* doesn't involve allocating. So the only issue I see it that the FIFO will march across memory. I guess that's probably not a problem as long as the GC knows it can reclaim the stuff you've popped off (Does it do that? Ie, if you do x = x[10..$]; and there's no other references, is the GC smart enough to reclaim those first ten spots? I guess I would assume so.)
Re: FIFO stack
Nick Sabalausky , dans le message (digitalmars.D.learn:30309), a écrit : Dominic Jones dominic.jo...@qmul.ac.uk wrote in message news:j89arh$2ua3$1...@digitalmars.com... Also an plain array is a good stack. :) I'd rather not use a plain array because (I assume) that when I push or pop using arrays, a swap array is created to resize the original. If this is not the case, then an array will certainly do. -Dominic The matter of using D's arrays as a LIFO is discussed the other branch of this thread (ie, you can do it, but it's slow because a pop then push will reallocate and copy), but as far as a FIFO: That may actually be reasonable to do as an array: Decreasing the length of an array (from either end) is a trivial matter that never allocates or copies. Appending to the end *usually* doesn't involve allocating. So the only issue I see it that the FIFO will march across memory. I guess that's probably not a problem as long as the GC knows it can reclaim the stuff you've popped off (Does it do that? Ie, if you do x = x[10..$]; and there's no other references, is the GC smart enough to reclaim those first ten spots? I guess I would assume so.) As far as I understand, if there is a pointer to an allocated memory block, the GC keeps the whole memory block. So the data at the beginning of x will be kept as long as x is not reallocated (but x will be reallocated at some point, because it can't walk across memory indefinitely, unless the GC is particularly efficient at avoiding reallocation). AFAIC, if I had to design a FIFO, I would use a circular array to avoid constant growing and reallocation of the array.
Re: FIFO stack
On Thu, 27 Oct 2011 08:00:31 -0400, Nick Sabalausky a@a.a wrote: Dominic Jones dominic.jo...@qmul.ac.uk wrote in message news:j89arh$2ua3$1...@digitalmars.com... Also an plain array is a good stack. :) I'd rather not use a plain array because (I assume) that when I push or pop using arrays, a swap array is created to resize the original. If this is not the case, then an array will certainly do. -Dominic The matter of using D's arrays as a LIFO is discussed the other branch of this thread (ie, you can do it, but it's slow because a pop then push will reallocate and copy), but as far as a FIFO: That may actually be reasonable to do as an array: Decreasing the length of an array (from either end) is a trivial matter that never allocates or copies. Appending to the end *usually* doesn't involve allocating. So the only issue I see it that the FIFO will march across memory. I guess that's probably not a problem as long as the GC knows it can reclaim the stuff you've popped off (Does it do that? Ie, if you do x = x[10..$]; and there's no other references, is the GC smart enough to reclaim those first ten spots? I guess I would assume so.) No, the granularity is on memory blocks. Once you slice off those first 10 elements, and you have no references to them, they become dead weight. But, as you append to the end, it will eventually outgrow its block, and the dead weight is *not* carried to the new block, so it will then be reclaimed. There are exceptions (such as when a block tacks on more pages). -Steve
Re: FIFO stack
On 10/27/11 8:38 AM, Nick Sabalausky wrote: Ary Manzanaa...@esperanto.org.ar wrote in message news:j89gle$9nn$1...@digitalmars.com... On 10/26/11 1:28 PM, Jonathan M Davis wrote: On Wednesday, October 26, 2011 09:00 Dominic Jones wrote: Also an plain array is a good stack. :) I'd rather not use a plain array because (I assume) that when I push or pop using arrays, a swap array is created to resize the original. If this is not the case, then an array will certainly do. -Dominic Not exactly. If you want to know more about how arrays work, you should read this: http://www.dsource.org/projects/dcollections/wiki/ArrayArticle It's a great read. As for using an array as a stack, you can do it with a wrapper struct, but using it by itself would result in a lot more reallocations than you'd want, as discussed here: https://www.semitwist.com/articles/article/view/don-t-use-arrays-as-stacks - Jonathan M Davis I think that if you have to read an article that long, with all the explanations of the different caveats a programmer can bump to when using them, to understand how arrays and slices work something must be wrong. Things should be simpler. FWIW, my article can be summarized with a line that's [poorly] located right around the middle (annotations added): Slicing an array is fast [no allocation or copying], and appending is usually fast [usually no allocation or copying], but slicing the end off and then appending is slow [does an allocate and copy]. I guess I have a habit of making things longer than they need to be ;) Nah, I liked your article, it assumes I know nothing and I like that. Maybe I did was exaggerating...
Re: FIFO stack
Ary Manzana a...@esperanto.org.ar wrote in message news:j8buhd$1s80$1...@digitalmars.com... On 10/27/11 8:38 AM, Nick Sabalausky wrote: Ary Manzanaa...@esperanto.org.ar wrote in message news:j89gle$9nn$1...@digitalmars.com... On 10/26/11 1:28 PM, Jonathan M Davis wrote: On Wednesday, October 26, 2011 09:00 Dominic Jones wrote: Also an plain array is a good stack. :) I'd rather not use a plain array because (I assume) that when I push or pop using arrays, a swap array is created to resize the original. If this is not the case, then an array will certainly do. -Dominic Not exactly. If you want to know more about how arrays work, you should read this: http://www.dsource.org/projects/dcollections/wiki/ArrayArticle It's a great read. As for using an array as a stack, you can do it with a wrapper struct, but using it by itself would result in a lot more reallocations than you'd want, as discussed here: https://www.semitwist.com/articles/article/view/don-t-use-arrays-as-stacks - Jonathan M Davis I think that if you have to read an article that long, with all the explanations of the different caveats a programmer can bump to when using them, to understand how arrays and slices work something must be wrong. Things should be simpler. FWIW, my article can be summarized with a line that's [poorly] located right around the middle (annotations added): Slicing an array is fast [no allocation or copying], and appending is usually fast [usually no allocation or copying], but slicing the end off and then appending is slow [does an allocate and copy]. I guess I have a habit of making things longer than they need to be ;) Nah, I liked your article, it assumes I know nothing and I like that. Maybe I did was exaggerating... Thanks. But you did have a good point, in fact it had already been nagging at me a little bit anyway: There's a very simple summary of the matter, but I didn't get around to spitting it out until halfway through. I've added a little thing to the top and feel a lot better about it now.
FIFO stack
Hello, I was looking for a FIFO stack in std.containers but only found SList and Array which both appear to essentially operate as LIFO stacks. Is there any standard container with which I can push items on to a list, then later pop them off from the bottom of that list? If so, then how? Thank you, Dominic Jones
Re: FIFO stack
On Wednesday, October 26, 2011 08:58:12 Dominic Jones wrote: Hello, I was looking for a FIFO stack in std.containers but only found SList and Array which both appear to essentially operate as LIFO stacks. Is there any standard container with which I can push items on to a list, then later pop them off from the bottom of that list? If so, then how? Nope. std.container is far from complete at the moment. It will eventually have all of the sundry containers that you'd expect in a standard library, but they haven't all been implemented yet, primarily because the custom allocator scheme that Phobos will be using hasn't been completely sorted out yet, and Andrei Alexandrescu (who is the primary designer and implementor of std.container) doesn't want to write them all and then have to go and change them all to be able to use custom allocators. In the meantime, you can take a look at http://dsource.org/projects/dcollections - Jonathan M Davis
Re: FIFO stack
On Wed, 26 Oct 2011 17:15:37 +0200, Simen Kjaeraas simen.kja...@gmail.com wrote: On Wed, 26 Oct 2011 10:58:12 +0200, Dominic Jones dominic.jo...@qmul.ac.uk wrote: Hello, I was looking for a FIFO stack in std.containers but only found SList and Array which both appear to essentially operate as LIFO stacks. Is there any standard container with which I can push items on to a list, then later pop them off from the bottom of that list? If so, then how? No such thing, sorry. Though writing one should be no big challenge. No such thing that is, if you don't want to use dCollections: http://www.dsource.org/projects/dcollections -- Simen
Re: FIFO stack
Am 26.10.2011, 17:20 Uhr, schrieb Simen Kjaeraas simen.kja...@gmail.com: On Wed, 26 Oct 2011 17:15:37 +0200, Simen Kjaeraas simen.kja...@gmail.com wrote: On Wed, 26 Oct 2011 10:58:12 +0200, Dominic Jones dominic.jo...@qmul.ac.uk wrote: Hello, I was looking for a FIFO stack in std.containers but only found SList and Array which both appear to essentially operate as LIFO stacks. Is there any standard container with which I can push items on to a list, then later pop them off from the bottom of that list? If so, then how? No such thing, sorry. Though writing one should be no big challenge. No such thing that is, if you don't want to use dCollections: http://www.dsource.org/projects/dcollections Also an plain array is a good stack. :)
Re: FIFO stack
Also an plain array is a good stack. :) I'd rather not use a plain array because (I assume) that when I push or pop using arrays, a swap array is created to resize the original. If this is not the case, then an array will certainly do. -Dominic
Re: FIFO stack
On 10/26/11 1:28 PM, Jonathan M Davis wrote: On Wednesday, October 26, 2011 09:00 Dominic Jones wrote: Also an plain array is a good stack. :) I'd rather not use a plain array because (I assume) that when I push or pop using arrays, a swap array is created to resize the original. If this is not the case, then an array will certainly do. -Dominic Not exactly. If you want to know more about how arrays work, you should read this: http://www.dsource.org/projects/dcollections/wiki/ArrayArticle It's a great read. As for using an array as a stack, you can do it with a wrapper struct, but using it by itself would result in a lot more reallocations than you'd want, as discussed here: https://www.semitwist.com/articles/article/view/don-t-use-arrays-as-stacks - Jonathan M Davis I think that if you have to read an article that long, with all the explanations of the different caveats a programmer can bump to when using them, to understand how arrays and slices work something must be wrong. Things should be simpler.
Re: FIFO stack
On Wednesday, October 26, 2011 10:38 Ary Manzana wrote: On 10/26/11 1:28 PM, Jonathan M Davis wrote: On Wednesday, October 26, 2011 09:00 Dominic Jones wrote: Also an plain array is a good stack. :) I'd rather not use a plain array because (I assume) that when I push or pop using arrays, a swap array is created to resize the original. If this is not the case, then an array will certainly do. -Dominic Not exactly. If you want to know more about how arrays work, you should read this: http://www.dsource.org/projects/dcollections/wiki/ArrayArticle It's a great read. As for using an array as a stack, you can do it with a wrapper struct, but using it by itself would result in a lot more reallocations than you'd want, as discussed here: https://www.semitwist.com/articles/article/view/don-t-use-arrays-as-stack s - Jonathan M Davis I think that if you have to read an article that long, with all the explanations of the different caveats a programmer can bump to when using them, to understand how arrays and slices work something must be wrong. Things should be simpler. Perhaps. But doing so and still having them be appropriately powerful is not straightforward if it's even possible. What we have works very well overall. It's just that if you start doing stuff that can cause an array to reallocate, and you don't understand enough about how arrays and slices work, you're going to end up reallocating your arrays way too often and harm performance. So, for the most part, you can use arrays just fine without understanding everything in that article, but your code risks being less efficient. Given how much you gain from D arrays, I think whatever complexity they have is _well_ worth it. It would be nice if the complexity could be reduced without reducing their usefuless or efficiency, but I don't know how possible that is. - Jonathan M Davis
Re: FIFO stack
Ary Manzana Wrote: On 10/26/11 1:28 PM, Jonathan M Davis wrote: Not exactly. If you want to know more about how arrays work, you should read this: http://www.dsource.org/projects/dcollections/wiki/ArrayArticle It's a great read. As for using an array as a stack, you can do it with a wrapper struct, but using it by itself would result in a lot more reallocations than you'd want, as discussed here: https://www.semitwist.com/articles/article/view/don-t-use-arrays-as-stacks - Jonathan M Davis I think that if you have to read an article that long, with all the explanations of the different caveats a programmer can bump to when using them, to understand how arrays and slices work something must be wrong. Things should be simpler. The thing is, it is simple. You can use them as a stack. But if performance matters to you, then you should be aware of how it operates. Or use something already built for performance for that use-case. Now it would be good if Arrays could be used for this, but that would make things more complicated, not less.
Re: FIFO stack
On 10/26/2011 07:38 PM, Ary Manzana wrote: On 10/26/11 1:28 PM, Jonathan M Davis wrote: On Wednesday, October 26, 2011 09:00 Dominic Jones wrote: Also an plain array is a good stack. :) I'd rather not use a plain array because (I assume) that when I push or pop using arrays, a swap array is created to resize the original. If this is not the case, then an array will certainly do. -Dominic Not exactly. If you want to know more about how arrays work, you should read this: http://www.dsource.org/projects/dcollections/wiki/ArrayArticle It's a great read. As for using an array as a stack, you can do it with a wrapper struct, but using it by itself would result in a lot more reallocations than you'd want, as discussed here: https://www.semitwist.com/articles/article/view/don-t-use-arrays-as-stacks - Jonathan M Davis I think that if you have to read an article that long, with all the explanations of the different caveats a programmer can bump to when using them, to understand how arrays and slices work something must be wrong. Things should be simpler. You exaggerate. The word 'caveat' appears exactly once in that article. The rest are straightforward explanations, mainly about how the runtime implements D array concatenation. After reading Steve's (actually quite short) article, you know about everything described in Nick's. D arrays and slices are so powerful that they are well worth a tiny little bit of complexity. The behaviour of dynamic arrays is a good trade-off between simplicity and performance imho.
