One of the first questions perl people ask when they try and use Pike is "where is shift()?!"
I've implemented simple versions of push(), pop(), shift() and unshift () for the Array module with refdoc pointers to ADT.Stack (arguably the correct place for them). Can someone with write access please commit it to modules/Array.pmod?
I'm willing to assign copyright to IDA because it's really only a few lines of code, but I do think it's a dumb policy.
Take care.
--- James Tyson I like to make things out of bits. http://helicopter.geek.nz/
On Mon, 26 Sep 2005 14:46:32 +1200 James Tyson james@thedogstar.org wrote:
I'm willing to assign copyright to IDA because it's really only a few lines of code, but I do think it's a dumb policy.
Its an excellent policy. Projects can end up with hundreds of random contributors over the years, and then if they need to change licensing terms for whatever reason, they basically can't. Good luck tracking down and getting permission from every single person. If the project is assigned copyright of all contributions, they can do whatever they want licensing wise.
Adam
On Mon, Sep 26, 2005 at 03:56:32PM -0400, Bill Welliver wrote:
hard to imagine that someone would want these functions, but i guess perl is pretty popular.
Those are most used functions in perl, at least shift() and push(). Wherever you need FIFO queues, those are a must.
Regards, /Al
that is right, but you should use ADT.Queue for that, and not a plain array, this is mostly a matter of people not finding the functions where they expect them...
greetings, martin.
that is right, but you should use ADT.Queue for that, and not a plain array, this is mostly a matter of people not finding the functions where they expect them...
Oops. I seealso'd to ADT.Stack, I'll change it :)
--- James Tyson Nothing Crashed, Nothing Gained http://helicopter.geek.nz/
Although arrays are rather optimized for operations like this now, compared to earlier, they are still arrays as in C-arrays. That means shift and unshift isn't necessarily a very smart operation. Tail functions, i.e push and pop, wouldn't typically be as bad (especially pop since that wouldn't have to change anything ever).
That said, list operations used to be incredibly slow when each operation reallocated the whole array.
Actually. shift/unshift. push/pop can simply use realloc and never have to actually copy all elements like the head operations do.
To clarify:
shift a => a = a[1..]; unshift a, value => a = ({value}) + a push a, value => a += ({ value }) pop a => a = a[..strlen(a)-2]
I don't know if unshift and push operations are optimized but I'm guessing they might be if there's free space on the head or tail of the array a.
Push is definitely. Unshift is too in theory, but it's difficult to make the optimization kick in. Also, you have to fix an array with spare room at the head, and that doesn't happen by itself.
The following program shows the optimization in action:
int main () { array a;
// This reallocates the array in every iteration. a = allocate (100000 - 10000); werror ("%O\n", gauge { for (int i = 0; i < 10000; i++) a = ({17}) + lambda () {array b = a; a = 0; return b;}(); });
// This does not reallocate the array in every iteration. a = allocate (100000); a = a[10000..]; werror ("%O\n", gauge { for (int i = 0; i < 10000; i++) a = ({17}) + lambda () {array b = a; a = 0; return b;}(); }); }
I get 30.82 sec in the first loop and 0.02 in the second with a 7.6. There are two things worth noting here:
o The line
a = ({17}) + lambda () {array b = a; a = 0; return b;}();
is essentially the same as "a = ({17}) + a", but the difference is that the array in a only exists on stack when `+ is executed. If you write
a = ({17}) + a;
you'll get two refs to the array: One in a and another on the stack in the call to `+. The optimizer has to play safe in that case and therefore can't change the array destructively.
o The lines
a = allocate (100000); a = a[10000..];
can't be combined to
a = allocate (100000)[10000..];
in 7.6 since the constant optimizer will produce an array with 90000 elements and no room before the head. This appears to work better in 7.7.
Because `+ is not allowed to be destructive on its arguments. It can therefore only be destructive as long as it isn't observable, and that's when there's no more than one ref to an argument.
But "a" on the left side, as a destination, doesn't need the array... Shouldn't that be possible to optimize?
Yes, it's possible to optimize. The optimization has to be to implicitly zero the variable a before the call to `+. The opcode used for x+=y actually already does that, but it's simpler to recognize that case. For the x=y+x case I think it'd be necessary to both have a treeopt rule and a new special opcode.
I was thinking more of a generic rule for
x=f(...,x,...)
since x doesn't have to keep it's value on the left side, it doesn't need a reference there.
I don't think it's safe to do that generically. Afterall, f might look at the value of x directly and it mustn't be zero then. It'd be safe to do if one could analyze that it isn't possible for f to access x in any way.
You mean the case
void func1() { array x;
...
void func2() { return x; }
x=func2(); }
where x shouldn't be without references during the call to func2?
Feels like that should be solved in some other way...
On Mon, Oct 03, 2005 at 01:55:05PM +0000, Marcus Comstedt (ACROSS) (Hail Ilpalazzo!) @ Pike (-) developers forum wrote:
Well, isn't the answer to that simply: "Here: [1..]"?
Not really. The [primary] purpose of shift() is to remove the 1st element, returning its value, while [1..] will only return the 1st element, without removing it.
Regards, /Al
Actually, it's the other way around, but I get your point. I assumed it worked like shift in /bin/sh.
pike-devel@lists.lysator.liu.se
-
Adam Montague -
Alexander Demenshin -
Bill Welliver -
David Hedbor (Amazon.com) ＠ Pike (-) developers forum -
James Tyson -
Marcus Agehall (PacketFront) ＠ Pike (-) developers forum
-
Marcus Comstedt (ACROSS) (Hail Ilpalazzo!) ＠ Pike (-) developers forum
-
Martin Bähr -
Martin Stjernholm, Roxen IS ＠ Pike developers forum
-
Mirar ＠ Pike developers forum