|
Posted by ~greg on March 22, 2008, 4:32 pm
Please log in for more thread options
I have always imagined arrays in Perl as contiguous stretches
of elements (pointers, or annotated pointers) in ram.
And push and pop as adding and removing from the right side,
without affecting more than one element.
Whereas I imagine shift and unshift as moving the whole
lot of them left and right. Which would make unshift and shift
considerably less efficient, time-wise, than push and pop.
Is that true? When modeling a stack, if there's a choice,
is using push and pop always preferable to using unshift and shift?
(For that reason, or any other?)
~greg
|
|
Posted by Gunnar Hjalmarsson on March 22, 2008, 4:37 pm
Please log in for more thread options
~greg wrote:
> I have always imagined arrays in Perl as contiguous stretches
> of elements (pointers, or annotated pointers) in ram. And push and pop
> as adding and removing from the right side, without affecting more than
> one element.
> Whereas I imagine shift and unshift as moving the whole lot of them left
> and right. Which would make unshift and shift
> considerably less efficient, time-wise, than push and pop.
> Is that true?
The latter can be easily measured with the Benchmark module.
--
Gunnar Hjalmarsson
Email: http://www.gunnar.cc/cgi-bin/contact.pl
|
|
Posted by Joost Diepenmaat on March 22, 2008, 4:53 pm
Please log in for more thread options
> Whereas I imagine shift and unshift as moving the whole lot of them
> left and right. Which would make unshift and shift
> considerably less efficient, time-wise, than push and pop.
this isn't completely true. see below.
> Is that true? When modeling a stack, if there's a choice, is using
> push and pop always preferable to using unshift and shift? (For that
> reason, or any other?)
perl keeps a pointer to the current head of the array inside the
actually allocated memory block, so a shift() followed by an unshift()
is likely to be just as fast as a pop() followed by a push().
If the allocated block is already full on the relevant side, though, I
suspect push() to be (much) more efficient than unshift() - at least if
standard malloc/re-alloc is used. Also, pop() and push() are the usual
names for stack operations, so if only for that reason you should
probably use them when modelling stacks.
side note: in languages that use linked lists to model stacks, pop and
push modify the start of the list.
See also the AV section in
http://www.perl.org/tpc/1998/Perl_Language_and_Modules/Perl%20Illustrated/
--
Joost Diepenmaat | blog: http://joost.zeekat.nl/ | work: http://zeekat.nl/
|
|
Posted by Abigail on March 22, 2008, 8:29 pm
Please log in for more thread options _
Joost Diepenmaat (joost@zeekat.nl) wrote on VCCCXVII September MCMXCIII
;;
;; > Whereas I imagine shift and unshift as moving the whole lot of them
;; > left and right. Which would make unshift and shift
;; > considerably less efficient, time-wise, than push and pop.
;;
;; this isn't completely true. see below.
;;
;; > Is that true? When modeling a stack, if there's a choice, is using
;; > push and pop always preferable to using unshift and shift? (For that
;; > reason, or any other?)
;;
;; perl keeps a pointer to the current head of the array inside the
;; actually allocated memory block, so a shift() followed by an unshift()
;; is likely to be just as fast as a pop() followed by a push().
;;
;; If the allocated block is already full on the relevant side, though, I
;; suspect push() to be (much) more efficient than unshift() - at least if
;; standard malloc/re-alloc is used. Also, pop() and push() are the usual
;; names for stack operations, so if only for that reason you should
;; probably use them when modelling stacks.
Perl uses its own malloc.
However, repeatedly pushing should be faster than repeated unshifting.
Whenever the allocated memory for the (C) array of SV pointers is full (or
when a boundary is reached), and the array increases beyond a boundary,
Perl allocates new memory, and copies the pointers over. The new slice
of memory will have about 20% surplus room - so an array can increases
for a while before reallocating is needed again. But this surplus room
will be at the end, so you can have many push()es before reallocating
is needed, but not so many unshift()s.
Abigail
--
$_ = "\x3C\x3C\x45\x4F\x54"; s/<<EOT/<<EOT/e; print;
Just another Perl Hacker
EOT
|
|
Posted by Ilya Zakharevich on March 23, 2008, 3:07 pm
Please log in for more thread options [A complimentary Cc of this posting was sent to
Abigail
> ;; If the allocated block is already full on the relevant side, though, I
> ;; suspect push() to be (much) more efficient than unshift() - at least if
> ;; standard malloc/re-alloc is used. Also, pop() and push() are the usual
> ;; names for stack operations, so if only for that reason you should
> ;; probably use them when modelling stacks.
> Perl uses its own malloc.
More often wrong than not.
> However, repeatedly pushing should be faster than repeated unshifting.
> Whenever the allocated memory for the (C) array of SV pointers is full (or
> when a boundary is reached), and the array increases beyond a boundary,
> Perl allocates new memory, and copies the pointers over. The new slice
> of memory will have about 20% surplus room - so an array can increases
> for a while before reallocating is needed again. But this surplus room
> will be at the end, so you can have many push()es before reallocating
> is needed, but not so many unshift()s.
??? This makes no sense.
If I read the current code (5.8.8) correct, unshift()ing may be slower
than push, since grow-for-unshift involves something realloc()ish,
then movement of pointers inside the C array. AND, unshift()ing may
be quickier than push, since it grows the C array in larger
increments.
Which tendency wins should depend on the details of the build of Perl.
Hope this helps,
Ilya
|
| Similar Threads | Posted | | unshift + loop? | November 30, 2005, 6:44 am |
| [NEWBIE] Trivial? | September 29, 2007, 1:39 am |
| Need help understanding an Array push | April 10, 2007, 11:33 am |
| push into hashs of arrays | August 24, 2007, 2:00 pm |
| MySql - push a hash into an array | October 2, 2006, 1:43 pm |
| How do I PUSH an HTTP::POST using perl LWP? | July 23, 2008, 6:26 pm |
| How to push some file to user, without show path of file? | December 1, 2005, 6:17 pm |
| Why isn't shift the same as $_[0]? | May 17, 2005, 9:45 am |
| what "shift" does, if not "$_ = shift;" ? | November 29, 2007, 1:25 pm |
| more efficient shift register? | May 25, 2006, 1:34 pm |
|
XML Sitemap