current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Stack Overflow is a community of 4.7 million programmers, just like you, helping each other.

Join them; it only takes a minute:

Sign up
Join the Stack Overflow community to:
  1. Ask programming questions
  2. Answer and help your peers
  3. Get recognized for your expertise
up vote 2 down vote favorite

First of all, I work with LispWorks. I have an adjustable array where I want to insert an element in position i < fill-pointer, so I will need to move all the elements from i to its position + 1. My problem is I don't know how to do that and have as result an adjustable array but WITHOUT COPYING all the elements to another array. Performance is really important. With this array #(0 1 2 3 4 6 7) my way to insert number 5 in position i=5:

(let ((arr (make-array 7 :initial-contents (list 0 1 2 3 4 6 7) 
                     :adjustable T :fill-pointer 7))
      (i 5)) 
    (concatenate 'vector (subseq arr 0 i)
                         (make-array 1 :initial-contents '(5))
                         (subseq arr i (fill-pointer arr))))

which I don't know if LispWorks is internally copying all elements to the result array, but gives me the desired array, although it is no adjustable and does not have fill-pointer. Some idea?

share|improve this question
up vote 2 down vote accepted

To increase optimization opportunities for your compiler, use specialized simple-array if possible; i.e., avoid fill-pointer and adjustable array. Also, higher level operation such as replace should allow memory to be moved in blocks (instead of one word at a time).

(defun insert-at (vec i val)
  (check-type vec (simple-array fixnum 1))
  (let ((new (make-array (1+ (length vec)) :element-type 'fixnum)))
    (declare (optimize speed))
    (setf (aref new i) val)
    (replace new vec :end1 i)
    (replace new vec :start1 (1+ i) :start2 i)))

Repeat 100 times to get more meaningful benchmark result(using sbcl):

(let ((arr (make-array 1000000 :element-type 'fixnum)))
  (time (loop repeat 100 for i from 500000 do
          (insert-at arr i i))))

Evaluation took:
  0.988 seconds of real time
  0.992062 seconds of total run time (0.804051 user, 0.188011 system)
  [ Run times consist of 0.148 seconds GC time, and 0.845 seconds non-GC time. ]
  100.40% CPU
  2,962,811,250 processor cycles
  800,003,200 bytes consed

Probably you should look at heap, which allows O(log n) insertion while maintaining (some sort of) order. Several implementations are available via quicklisp.

share|improve this answer
    
Thanks, I tried this version and the one proposed below. This one is slightly faster and in my opinion simpler too. – Francis Jun 12 '13 at 11:31
    
This calls replace twice and allocates an intermediate array. – sds Jun 12 '13 at 12:44
    
@sds: I ran again a similar benchmark but with fill-pointer and adjustable array, and insert-into-array (the latter version that uses replace) took twice as long under SBCL. I suppose this kind of micro-optimization is highly implementation-dependent; but at least with SBCL, the benefit of simple-array outweighs the saving from reduced data movements modulo the cost of keeping the array adjustable. Relocation is unavoidable even for vector-push-extend when the extended array can no longer fit in the old space. – huaiyuan Jun 12 '13 at 16:21
    
OP wanted to preserve the fill-pointer and adjustability. I am actually surprised that in SBCL implementing adjustability "by hand" (which is what you are doing!) is better than using the adjustable arrays in the first place. – sds Jun 12 '13 at 16:37
    
Specialized arrays also has drawbacks. If one is not using high optimizations, they may be slower than a un-specialized array. – Rainer Joswig Oct 4 '13 at 7:47
up vote 3 down vote

First of all, your code conses far too much.

Here is a version which conses as little as possible:

(defun insert-into-array (vector value position)
  (vector-push-extend value vector) ; ensure that the array is large enough
  ;; shift the end of the array right
  (loop for i from (1- (length vector)) downto (1+ position) do
      (setf (aref vector i) (aref vector (1- i))))
  (setf (aref vector position) value) ; insert value into the right place
  vector)
(insert-into-array (make-array 9 :initial-contents '(0 1 2 3 4 6 7 8 9) 
                                 :adjustable T :fill-pointer 9) 5 5)
==> #(0 1 2 3 4 5 6 7 8 9)

Note that this will do N assignments in the worse case, so, if insertion is a common operation in your setup and you do not need random access, you might want to consider linked lists instead of arrays.

EDIT: I forgot about replace, which makes the loop unnecessary:

(defun insert-into-array (vector value position)
  (replace vector vector :start2 position :start1 (1+ position) 
           :end2 (vector-push-extend value vector))
  (setf (aref vector position) value) 
  vector)
share|improve this answer
    
Yes, I know how to copy in a new array, but even though insertion is not really common operation, I need it with certain level of performance. I tried with your code and an array of 1M elements to insert in middle. Just do it one time takes 2.5seconds in my computer, while my code above did it in 0.1sec. Your solution works, it's the same I have so far, but I would like something like I proposed, without N assignments in worst case or N/2 in average. Could you do it without going through the array? I mean, concatenating beginning and end of arrays, instead of assigning elements 1 by 1? – Francis Jun 9 '13 at 17:16
1  
Did you compile the code? The only other reason for your code to outperform mine is if LW has a superfast internal array copy routine - something like memmove(3). Find it and use it instead of the loop. Basically, your code does strictly more assignments (plus memory allocation!) than mine, so, if it is faster, you need to ask the vendor. – sds Jun 9 '13 at 17:31
    
Yep, true, I forgot. Works fine then. Anyway, the code I'm using (not the one I wrote) does same as yours, but unless there is some low level way of copying bigger blocks of memory more efficiently, like memmove, in LW, I think I will need to keep this one. – Francis Jun 9 '13 at 19:54
    
see edit - try replace – sds Jun 9 '13 at 20:38
    
Hello Francis, depending on the element type of your array it might be interesting to try with a foreign array, i.e. a linear chunk of memory allocated in static area. You can then use replace-foreign-array which is extremely fast. This, of course, comes at the price of flexibility. – tuscland Jun 10 '13 at 6:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.