1

I am working on the code below in Matlab. When you make bigger the parameters it takes too much time to finish run. Then I want to optimize the code to make it run faster. I didnt take any algorith optimization course yet. However I have changed some parts of it. The code is faster now but, it is not enough.

Do you have an idea guys to make it faster? Preallocation, initializing before-later, whatever..

rand('state', sum(100*clock));
runs=10000;
bw=20000; ttimeout=303/bw; ts=20/bw;
sift_times=[];sift_tcolls=[];sift_tcws=[];

range_n=5;
for n = range_n
  sift_collisions=[]; 
  uniform_collisions=[]; 
  for w=3:63
      uniform_collision=0;
      sift_collision=0;      
      for i=1:runs
            %Sift Dist:
            chosen_slots = sift_assign_slots(w,n);
            [slots,nodes] = sort(chosen_slots);
            if (slots(1)==slots(2))
                sift_collision = sift_collision + 1;
            end
            %Uniform Dist:
            chosen_slots = ceil(w*rand(n,1));
            [slots,nodes] = sort(chosen_slots);
            if (slots(1)==slots(2))
                uniform_collision = uniform_collision + 1;
            end
        end
        sift_collisions (w-2) = sift_collision  ;
        uniform_collisions(w-2) = uniform_collision  ;
  end
end
user2870
  • 477
  • 7
  • 18
  • 5
    You said it: _preallocation_. There are too many empty matrices hanging around here! – Eitan T Sep 11 '13 at 10:25
  • How to do it, where, on which variable? – user2870 Sep 11 '13 at 10:25
  • 1
    Have you read [this article](http://www.mathworks.com/support/solutions/en/data/1-18150/)? Or [this question](http://stackoverflow.com/q/17424921/1336150)? – Eitan T Sep 11 '13 at 10:28
  • 2
    Yeah I agree with EitanT, you're building a large matrix (63x3) there within your loops. Preallocating might just decrease your run time enormously. – Fraukje Sep 11 '13 at 10:31
  • 1
    @EitanT: do you happen to know *why* MATLAB requires arrays to be stored in *contiguous* memory? That is the main reason pre-allocation is required in MATLAB (and not in say, C) – Rody Oldenhuis Sep 11 '13 at 10:42
  • Before having people guess what might make your code faster - why not use `profile` to first have a look at which lines are actually slowing you down? The `for i=1:runs` loop for instance runs 10000 times for each outer loop, calling `sift_assign_slots` whose body we don't know...which makes me doubt that the missing preallocation of the not-really-large 3*63 matrix is the bottleneck – sebastian Sep 11 '13 at 11:39
  • 1
    @RodyOldenhuis: all proper(†) programming languages require arrays to be stored contiguously so that elements can be accessed by a simple calculation `base address+index` (where `index` may require integer arithmetic for arrays of rank>1). Pointers, and hopping around memory from address to address, not required. (†)If a language does not store arrays contiguously it is not a proper language. – High Performance Mark Sep 11 '13 at 12:07
  • 1
    @HighPerformanceMark Instead of allocating a contiguous chunk of memory for the data itself, we can allocate a a contiguous chunk of memory just for pointers, each pointing at an element stored in a different part in the memory. Fetching a pointer via an index can be also done by means of a simple calculation, hence accessing an element is merely a matter of dereferencing the pointer. – Eitan T Sep 11 '13 at 12:28
  • @RodyOldenhuis I think the requirement for contiguous memory comes from the need for fast copies. Copying contiguous memory-aligned chunks of data can be _much much_ faster than hopping around the memory. Since MATLAB uses a lot of copies, I imagine that this can be pretty significant. By the way, preallocation is implicitly done in C when you define arrays (so it's not a matter of choice!). – Eitan T Sep 11 '13 at 12:38
  • @HighPerformanceMark: But MATLAB requires contiguous blocks in the *virtual address space*. I must be misunderstanding something, so please correct me where necessary. As I understand it, the virtual address space is a simple mapping between some abstract address and a real location in physical memory. This would imply that *real* locations of MATLAB's data are generally still fragmented in RAM, and the advantages of contiguous data (cache-friendliness) is lost. This makes MATLAB's demand seem completely futile... – Rody Oldenhuis Sep 11 '13 at 13:33
  • @EitanT: true, but C uses a smarter dynamic array; resize the array by N elements (instead of just 1) to prepare for any future insertions. This is less lossy in loops. I suspect TMW switched to this sort of logic in R2011a and up... – Rody Oldenhuis Sep 11 '13 at 13:36
  • @RodyOldenhuis I'm not following, are you talking about `realloc` in C? – Eitan T Sep 11 '13 at 13:39
  • @EitanT: no, [dynamic arrays](http://en.wikipedia.org/wiki/Dynamic_array). It's like `std::vector` in C++, but there are tons of versions of this in C as well. – Rody Oldenhuis Sep 11 '13 at 13:47
  • let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/37184/discussion-between-rody-oldenhuis-and-eitan-t) – Rody Oldenhuis Sep 11 '13 at 14:09

0 Answers0