Community
Participate
Working Groups
PointList performance hit due to unnecessary re-allocation and arrayCopy in ensureCapacity and toIntArray. Problem # 1 - ensureCapacity ensureCapacity is invoked when addPoint() is used to add a point. It however do new int and arrayCopy if (newSize < size). This loses the advantage of pre- allocation using the ctor PointList(int size) to allocate the points[] to a given capacity, because size is always < newSize. Adding points subsequently will re-alloc and arrayCopy for each additional point. It should "new int" and arrayCopy if (newSize * 2 > points.length) Client Test code: PointList pl = new PointList(10000); for (int i = 0; i < 10000; i++) { pl.add(...); // will see new int and arrayCopy for each iteration } Suggested fix: private void ensureCapacity(int newSize) { //if (size < newSize) { // FIX: performance hit - wlai if (newSize * 2 > points.length) { int old[] = points; newSize = Math.max(newSize, size * 3 / 2); points = new int[newSize * 2]; System.arraycopy(old, 0, points, 0, size * 2); } } Problem # 2 - toIntArray toIntArray() shrinks the points[] to its current size. Adding points to the PointList object loses the advantage of capacity pre-allocated in ctor. It should alloc a temp array, copy the content over and return the temp array if (points.length != size * 2). Clinet test code: PointList pl = new PointList(10000); for (int j = 0; j < 20; j++) { for (int i = 0; i < 10000; i++) { pl.add(...) // if something happens, break this inner loop } graphics.drawPolyline(pl); // call toIntArray(), PointList.size may be < 10000 pl.removeAllPoints(); } Suggested fix: public int[] toIntArray() { if (points.length != size * 2) { int[] old = points; // [ FIX: performance hit - wlai //points = new int[size * 2]; //System.arraycopy(old, 0, points, 0, size * 2); int[] temp = new int[size * 2]; System.arraycopy(old, 0, temp, 0, size * 2); return temp; // ] } return points; }
This performance issue is tested against 3.1m6. What is the work-around if it cannot be solved in 3.1m7?
The purpose of PointList is to make painting an array of ints convenient in SWT. Since SWT requires the exact length int array, and since painting occurs orders of magnitude more often than modification of a given point list in general, we cache the exact-length int array. So, problem #2 will not be fixed. One workaround is to not use PointList.
How does this look. It's the same as what you suggested I think, except I'm multiplying by 2 earlier to avoid the additional multiply+divide, private void ensureCapacity(int newSize) { newSize *= 2; if (points.length < newSize) { int old[] = points; points = new int[Math.max(newSize, size * 3)]; System.arraycopy(old, 0, points, 0, size * 2); } }
(In reply to comment #3) > How does this look. It's the same as what you suggested I think, except I'm > multiplying by 2 earlier to avoid the additional multiply+divide, > private void ensureCapacity(int newSize) { > newSize *= 2; > if (points.length < newSize) { > int old[] = points; > points = new int[Math.max(newSize, size * 3)]; > System.arraycopy(old, 0, points, 0, size * 2); > } > } That's perfect and will be great if it will be delivered in 3.1M7
(In reply to comment #2) > The purpose of PointList is to make painting an array of ints convenient in > SWT. Since SWT requires the exact length int array, and since painting occurs > orders of magnitude more often than modification of a given point list in > general, we cache the exact-length int array. So, problem #2 will not be fixed. > One workaround is to not use PointList. Will you consider to change ensureCapacity to public method and add new API to getCapacity() that returns points.length? I was thinking to use setSize as a work-around to tackle my concern on toIntArray() as shown below PointList pl = new PointList(10000); for (int j = 0; j < 20; j++) { for (int i = 0; i < 10000; i++) { pl.add(...) // if something happens, break this inner loop } graphics.drawPolyline(pl); // call toIntArray(), PointList.size may be < 10000 pl.removeAllPoints(); pl.setSize(10000); } But then (i) If newSize * 2 == points.length, setSize still do "new int" and arrayCopy (ii) I don't really intend to copy point's content (points.length) over to the new array because my desire is to clear content while ensuring capacity for next iteration. That means I should not use setSize() for this purpose.
The (now corrected) behavior of addPoint() is that it will resize and copy the array at most O(Log(n)) times. So, adding 10,000 items will require something like 12 copies.
(In reply to comment #6) > The (now corrected) behavior of addPoint() is that it will resize and copy the > array at most O(Log(n)) times. So, adding 10,000 items will require something > like 12 copies. Are you saying you won't fix ensureCapacity as you suggested in Comment #3? I would suggest to fix ensureCapacity in addition the improvement of addPoint(), because it will be 0 resize and copy compared to 12 times. I don't see anyone would give up 0 copy and go for 12 times if the former case can be achieved.
Released to HEAD > 0504
