Update!
We wrote a containers.Map backed list class. Build up the list using the “append” method, and then assign the values to a cell array using “toCell” to iterate them (don’t use valueByIndex). Building up the list is still slow, but iterating is lightning fast! You’ll also need this noop Null class.
As of 2008b Matlab only has one abstract data type built-in: containers.Map. I needed a typical List class, and thought I’d back it with a cell array ala Java’s ArrayList. I was surprised to find that accessing a cell as the property of an object was a huge performance bottleneck.
Mathworks has this to say about passing behavior:
“In the case of passing structures or cell arrays, only the field or cell data being modified by the function will be passed “by value”. When the function returns, (assuming that the modified structure or cell array is returned as an output argument of the function) the calling workspace’s copy of the structure or cell array is replaced by the function’s copy such that only the changed fields are altered. This is done to make copying more efficient.”
Are my slowdowns due to some unnecessary copying? Or is it just the overhead of making method calls? Here are some simple benchmarks:
%classdef CellList % properties % cellArray = cell(1000, 1); % end % % methods % function setIndex(self, index, value) % self.cellArray{index} = value; % end % end %end list1 = CellList(); tic for i = 1 : 1000 list1.setIndex(i, 'foo'); end toc list2 = cell(1000, 1); tic for i = 1 : 1000 list2{i} = 'foo'; end toc %function my_setindex(alist, i) % alist{i} = 'foo'; %end list3 = cell(1000, 1); tic for i = 1 : 1000 my_setindex(list3, i); end toc Elapsed time is 0.122691 seconds. Elapsed time is 0.000306 seconds. Elapsed time is 0.020764 seconds.
So inserting into a “preallocated” cell from a function is two orders of magnitude slower than manipulating a variable directly, and doing it with a method accessing a cell array stored in a property is 10x slower still.
Scott suggests we try using Matlab’s copy-in-place strategy in his comment below. This yields:
%function ret = my_setindex2(alist, i) % alist{i} = 'foo'; % ret = alist; %end list4 = cell(1000, 1); tic for i = 1 : 1000 list4 = my_setindex2(list4, i); end toc Elapsed time is 0.057074 seconds.
Seems to take a little longer still than the non assigning function call we did previous. Maybe cell arrays are more difficult for the accelerator to work with.
So how much of this is due to the built-in overhead of calling functions and methods? The time in our first example to insert 1000 elements directly into a cell array was 3.06e-4. If we add this to 1000 invocations of a NOOP function and method in turn, should we get the 1.23e-1 and 2.08e-2 we saw for their cell inserting counterparts?
%classdef Foo % methods % function bar(self) % end % end %end aFoo = Foo(); tic for i = 1 : 1000 aFoo.bar(); end toc %function baz() %end tic for i = 1 : 1000 baz(); end toc Elapsed time is 0.056698 seconds. Elapsed time is 0.001112 seconds.
Doesn’t look like it. Still around an order of magnitude unaccounted for in the function version, and perhaps half as much for the method.
I ended up going with a linked list. This is another of Scott’s suggestions. For what I was working on at the time, it eliminated list appends from the top ten in the profiler, but strangely I can’t trivially reproduce the speed-up in isolation:
%classdef ListNode % properties % next; % value; % end %end n = ListNode(); n.value = 'foo'; tic for i = 1 : 1000 nn = ListNode(); nn.value = 'foo'; n.next = nn; n = nn; end toc Elapsed time is 0.221035 seconds.
Sorry there aren’t many answers here. Maybe this post will garner more comments.
Attached are a fairly featureful LinkedList and LinkedListIterator class that I wrote. These are generously provided under an open source license by my employer.
