Re: Efficiency/Reliablility of Scaled Up JTable

[Eric Sosman]

On 4/29/2013 8:13 AM, clusa...@aol.com wrote:
> If I have a JTable with a lot of colors, and if the application deletes and then adds columns to it will the performance degrade if I go from a 30 X 30 table to a 1000 X 100 table, please explain.

If you're being reasonably careful,[*] the performance
shouldn't be bad. Remember, only the visible portion of the
table needs painting,[**] so only the visible cells' values
need to be retrieved and rendered. Off-screen areas won't
affect the performance much.

Using many -- or few -- colors should make no measurable
difference.

[*] For example, firing "minimal" change events. If your
model changes one cell's value and then says "The world has
changed," the table will spend time refreshing all the cells
that didn't change, too. Fire events that describe the actual
changes as particularly as possible.

[**] If you're displaying all 100,000 cells simultaneously,
you either (1) have a truly enormous screen or (2) have made
all the cells so tiny they can't show much information. My
1920x1080 display could devote fewer than 21 pixels to each of
100,000 cells, fewer pixels than a mouse pointer uses -- and
that's not counting borders, window decorations, ...

--
Eric Sosman
eso...@comcast-dot-net.invalid

[Daniel Pitts]

On 4/29/13 5:13 AM, clusa...@aol.com wrote:
> If I have a JTable with a lot of colors, and if the application deletes and then adds columns to it will the performance degrade if I go from a 30 X 30 table to a 1000 X 100 table, please explain.
>

> Thanks,
>
It depends on the underlying TableModel implementation. Using the
default implementation, it is backed by a Vector of Vectors [1].
A "random position" insert or remove in a vector is amortized to be an
O(N) operation. insert/remove at the end of a vector is O(1).

Adding a row will create a brand new Vector, and insert that Vector into
the row Vector. remove a row will simply remove that row from the row
Vector.

Adding or remove a column will need to iterate through all rows and
add/remove from each of the column Vectors. If this is the first
column, your worst case, this will be a O(N*M) operation.

So, for a 1000 x 100 table:

Best case scenario of deleting the last row is fast constant time operation.

Worst case scenario (deleting or inserting the first column) is 10,000
operations. That is, for each 1000 rows, you need to touch each of the
100 columns.

Now, some estimations... I'm going to estimate that one "operation" (a
reference copy in this case) takes 50 CPU cycles to complete. This is a
high estimate, but may be affected by memory latency and other system
delays. Now, if your processor is at least 1GHz, that means a single
"operation" will take 50ns. 10,000 operations will take 500�s. Human
perception around 250ms, meaning you could do this worst-case update 500
times before a human would even notice that anything was changing.

Next, when you insert/delete a row or column, the UI has to repaint the
"visible" portion of your table. The timing on this is likely going to
be the expensive part of operation. However, if you are only looking at
a 30x30 cell viewport into the table, the performance of this will be
nearly the same regardless of the overall table size.

Hope this helps,
Daniel.


[1]
<http://docs.oracle.com/javase/7/docs/api/javax/swing/table/DefaultTableModel.html>

[Eric Sosman]

On 4/29/2013 11:26 AM, Daniel Pitts wrote:
> On 4/29/13 5:13 AM, clusa...@aol.com wrote:
>> If I have a JTable with a lot of colors, and if the application
>> deletes and then adds columns to it will the performance degrade if I
>> go from a 30 X 30 table to a 1000 X 100 table, please explain.
>>
>> Thanks,
>>
> It depends on the underlying TableModel implementation. Using the
> default implementation, it is backed by a Vector of Vectors [1].
> A "random position" insert or remove in a vector is amortized to be an
> O(N) operation. insert/remove at the end of a vector is O(1).
>
> Adding a row will create a brand new Vector, and insert that Vector into
> the row Vector. remove a row will simply remove that row from the row
> Vector.
>
> Adding or remove a column will need to iterate through all rows and
> add/remove from each of the column Vectors. If this is the first
> column, your worst case, this will be a O(N*M) operation.

> [...]

Good stuff. However, didn't the O.P. have a question a day
or so ago about a "horizontally scrolling" table, where new columns
appeared at the right while old ones vanished from the left (maybe
with a few leftmost columns inviolate)? If that's the table in
question, I think he'd do better to use a column-oriented model,
where the vectors (not necessarily Vectors) run top-to-bottom
instead of left-to-right. A benefit would be that inserting,
deleting, and permuting columns could be done by I/D/P'ing the
vector references instead of mucking with the individual cell
contents.

It all depends on which axis gets more activity.

Alternatively, a HashMap<Pair<Integer,Integer>,Object> might
serve as model supporting both access directions equally well,
and could handle row/column rearrangements quickly by storing
"virtual" coordinates translated through a pair of arrays for
the permutation of the moment.

--
Eric Sosman
eso...@comcast-dot-net.invalid

[Robert Klemme]

On 04/29/2013 02:13 PM, clusa...@aol.com wrote:
> If I have a JTable with a lot of colors, and if the application
> deletes and then adds columns to it will the performance degrade if I
> go from a 30 X 30 table to a 1000 X 100 table, please explain.

I suggest to measure instead of speculate where the time is spent.
There are even free tools to do that (e.g. -Xrunhprof and HP JMeter).

Cheers

robert

[Daniel Pitts]

On 4/29/13 9:01 AM, Eric Sosman wrote:
> On 4/29/2013 11:26 AM, Daniel Pitts wrote:
>> On 4/29/13 5:13 AM, clusa...@aol.com wrote:
>>> If I have a JTable with a lot of colors, and if the application
>>> deletes and then adds columns to it will the performance degrade if I
>>> go from a 30 X 30 table to a 1000 X 100 table, please explain.
>>>
>>> Thanks,
>>>
>> It depends on the underlying TableModel implementation. Using the
>> default implementation, it is backed by a Vector of Vectors [1].
>> A "random position" insert or remove in a vector is amortized to be an
>> O(N) operation. insert/remove at the end of a vector is O(1).
>>
>> Adding a row will create a brand new Vector, and insert that Vector into
>> the row Vector. remove a row will simply remove that row from the row
>> Vector.
>>
>> Adding or remove a column will need to iterate through all rows and
>> add/remove from each of the column Vectors. If this is the first
>> column, your worst case, this will be a O(N*M) operation.
>> [...]
>
> Good stuff. However, didn't the O.P. have a question a day
> or so ago about a "horizontally scrolling" table, where new columns
> appeared at the right while old ones vanished from the left (maybe
> with a few leftmost columns inviolate)?

Perhaps, I skipped over it if that was the case.

> If that's the table in
> question, I think he'd do better to use a column-oriented model,
> where the vectors (not necessarily Vectors) run top-to-bottom
> instead of left-to-right. A benefit would be that inserting,
> deleting, and permuting columns could be done by I/D/P'ing the
> vector references instead of mucking with the individual cell
> contents.

That might be a benefit, if indeed the pre-written and well-tested
DefaultTableModel doesn't perform "well enough" for the real use-case at
hand.

>
> It all depends on which axis gets more activity.

It also depends on what minimum performance is necessary, and what the
maximum amount of engineering is allowed to be put into this use-case.

>
> Alternatively, a HashMap<Pair<Integer,Integer>,Object> might
> serve as model supporting both access directions equally well,
> and could handle row/column rearrangements quickly by storing
> "virtual" coordinates translated through a pair of arrays for
> the permutation of the moment.>

Supporting Access yes, but imagine now an insert into either the first
row *or* the first column. You now have to go through *every* key of
this hashmap, and build a brand-new hashmap with the adjusted Pair
object (remember, it is a bug to change the value of a Key object). This
increases the number of "worst-case" insertions, and I believe doubles
the average-case cost.

In any case, I suspect that the default model *should* be sufficient.
The OP would do well to write a quick test which plays out some mock
activity to match situations which are expected. The only way to know
for sure is to try. My previous analysis was basically to show that
"you are in the ball-park of being okay".

--
Daniel.

[Eric Sosman]

On 4/29/2013 4:09 PM, Daniel Pitts wrote:
> On 4/29/13 9:01 AM, Eric Sosman wrote:

>> [...]

>> Alternatively, a HashMap<Pair<Integer,Integer>,Object> might
>> serve as model supporting both access directions equally well,
>> and could handle row/column rearrangements quickly by storing
>> "virtual" coordinates translated through a pair of arrays for
>> the permutation of the moment.>
> Supporting Access yes, but imagine now an insert into either the first
> row *or* the first column. You now have to go through *every* key of
> this hashmap, and build a brand-new hashmap with the adjusted Pair
> object (remember, it is a bug to change the value of a Key object). This
> increases the number of "worst-case" insertions, and I believe doubles
> the average-case cost.

I don't think there's any really slick way to insert a new
cell in the middle of the grid and shove the neighbors rightward
and downward, nor (dually) to delete a cell and pull the neighbors
leftward and upward. But if all he needs to do is insert or delete
an entire row or column, that's what the permutation arrays (or
lists) are for. Somebody wants to access row r, column c, and you
look in the HashMap for coordinates rowmap[r],colmap[c] instead.
To insert a new row at the r'th position, copy rowmap[r] through
rowmap[n-1] to rowmap[r+1] through rowmap[n], store a brand-new,
previously unused coordinate value in rowmap[r], and off you go
with the existing HashMap keys unchanged.

Mind you, I haven't actually *done* this for a TableModel, and
there may be kinks and snags I haven't thought of. Seems like an
approach that wouldn't penalize one axis to favor the other, though.

> In any case, I suspect that the default model *should* be sufficient.
> The OP would do well to write a quick test which plays out some mock
> activity to match situations which are expected. The only way to know
> for sure is to try. My previous analysis was basically to show that
> "you are in the ball-park of being okay".

Agreed: Measure, measure, measure beats guess, guess, guess.

--
Eric Sosman
eso...@comcast-dot-net.invalid

[Roedy Green]

On Mon, 29 Apr 2013 05:13:44 -0700 (PDT), clusa...@aol.com wrote,
quoted or indirectly quoted someone who said :

>If I have a JTable with a lot of colors, and if the application deletes and then adds columns to it will the performance degrade if I go from a 30 X 30 table to a 1000 X 100 table, please explain.

JTable scalability depends mainly on the efficiency of your
TableModel. All JTable does is render one screenful of your table. No
matter how big the table, it is roughly the same amount of work other
than what your TableModel does.
--
Roedy Green Canadian Mind Products http://mindprod.com
Nothing is so good as it seems beforehand.
~ George Eliot (born: 1819-11-22 died: 1880-12-22 at age: 61) (Mary Ann Evans)

[Eric Sosman]

On 5/1/2013 3:41 PM, clusa...@aol.com wrote:

>> On Monday, April 29, 2013 12:01:11 PM UTC-4, Eric Sosman wrote:
>> However, didn't the O.P. have a question a day or so ago about
>> a "horizontally scrolling" table, where new columns appeared at the right
>> while old ones vanished from the left (maybe with a few leftmost columns
>> inviolate)? If that's the table in question, I think he'd do better to use a
>> column-oriented model, where the vectors (not necessarily Vectors) run top-to-
>> bottom instead of left-to-right. A benefit would be that inserting, deleting,
>> and permuting columns could be done by I/D/P'ing the vector references
>> instead of mucking with the individual cell contents. It all depends on which
>> axis gets more activity.
>

> Q1. Can anyone point me towards example code that uses a column-oriented model, that would help me think about developing a table like I want. How many different types of column-oriented models are there anyway.

*I* can't, but it seems straightforward enough. DefaultTableModel
uses a Vector for each table row (at least, that's what methods like
getDataVector() produce). When the model refers to the cell at row r,
column c, it uses something like

Vector<Vector<Object>> allRows = ...
...
Vector<Object> rthRow = allRows.get(r);
Object cell = rthRow.get(c);

With this arrangment it's easy to add a row, delete a row, or
rearrange the rows: You do everything to the allRows Vector, and
the individual row contents move around as units. But column
operations are harder: To delete a column, for example, you've
got to go through all the row Vectors deleting one cell from each.
If the column operations are what's important, you could turn
things around:

Vector<Vector<Object>> allCols= ...;
...
Vector<Object> cthCol = allCols.get(c); // note r/c reversal
Object cell = cthCol.get(r);

Now it's easy to manipulate the columns as units -- but it's
harder to fiddle with the rows. TANSTAAFL.

>> Alternatively, a HashMap<Pair<Integer,Integer>,Object> might serve as model
>> supporting both access directions equally well, and could handle row/column
>> rearrangements quickly by storing "virtual" coordinates translated through a > pair of arrays for the permutation of the moment.
>

> Q2. Can anyone point me towards example code that uses a HashMap model (colors cells etc) for my table (containing textural data), and be able of helping me think about this efficiency problem some more.

As I mentioned elsethread, it's just an idea: I haven't actually
tried it, nor seen it used. My thought was that this could be a way
to handle both row and column operations with comparable ease.

(You keep mentioning cell colors, as if you somehow expect them
to affect the performance. I cannot imagine why you'd think they
would, so I suspect I'm failing to understand all of your problem.)

> Q3. Not considering efficiency, would I gain or lose "anything" else if I switched from the regular JTable model to either a column-oriented or HashMap model. For example, would one of the alternatives require more code to do things.

Either alternative would probably require you to write more code
than if you just used DefaultTableModel.

At this point I think I should echo (or paraphrase) Daniel
Pitts: Is this work necessary? That is, do you have evidence that
a plain vanilla JTable with DefaultTableModel is inadequate? If
you don't, all this fretting may be doing nothing except raise your
blood pressure: Just write the plain-vanilla version, measure how
well or poorly it works, and *then* decide whether to do extra work.

--
Eric Sosman
eso...@comcast-dot-net.invalid

[John B. Matthews]

In article <57924ab7-1b72-4f7f...@googlegroups.com>,
clusa...@aol.com wrote:

> [...]

> Q1. Can anyone point me towards example code that uses a column-
> oriented model, that would help me think about developing a table
> like I want. How many different types of column-oriented models are
> there anyway.

JTable maintains a TableColumnModel in which each "TableColumn stores
the link between the columns in the JTable and the columns in the
TableModel." In this way columns in the view (JTable) can be {added,
moved, removed} without having to alter data in the model (TableModel).
A TableColumn also lets you specify renderers and editors on a per
column basis.

> [...]

> Q2. Can anyone point me towards example code that uses a HashMap
> model (colors cells etc) for my table (containing textural data), and
> be able of helping me think about this efficiency problem some more.

This minimal example builds a TableModel around the Map returned by
System.getenv():

<http://stackoverflow.com/a/9134371/230513>

Editors and renderers are covered here:

<http://docs.oracle.com/javase/tutorial/uiswing/components/table.html>

> Q3. Not considering efficiency, would I gain or lose "anything" else
> if I switched from the regular JTable model to either a
> column-oriented or HashMap model. For example, would one of the
> alternatives require more code to do things.

JTable uses the flyweight pattern to render visible cells. The default
renderers perform very well, but it's not hard to introduce latency in a
custom implementation. Profile to be sure.

This example easily handles thousands of rows. The default renderer and
editor for a value of type Boolean.class is a JCheckBox. Increase the
number of rows and add more columns to see how it scales.

<http://stackoverflow.com/a/13919878/230513>

--
John B. Matthews
trashgod at gmail dot com
<http://sites.google.com/site/drjohnbmatthews>