Increasing the row limit above 32000 rows
Table of content
- Document structure overview
- Position accessing methods
- List of structs and classes having an USHORT (or short or UINT16 or INT16) row value as member variable
- List of defines using a limited row value
- Some specials about row numbers
- Road map and time frame
- Table of steps
Currently the spreadsheet application is limited to 32000 rows per sheet. As we all know that is not enough for some uses. In this document I will describe the code changes which have to be done to increase the limit. Where necessary I will also insert some remarks about why the code is like it is, pitfalls and things to have in mind when changing the code. This document is under development, the goal is to have it completed by the end of the year, so changing the code may start next year (apart from some minor changes here and there which can be done on the fly). [Editor's note: that was back in 2001. The goal was shifted twice because of other tasks to be completed with higher priority. Hopefully we'll start modifying code by the end of July / start of August 2002]. You may wonder about that time frame, but increasing the row limit is not a task of changing one defined constant or similar. You will see as this document evolves.
Bear in mind that most document structures were designed back in old Win31 days and the number of rows was limited to 8192 then. Win31 couldn't address more than 64kB in one contiguous memory area without huge effort (it could have been 16384 instead of 8192 (what the unnamed competitors program implemented in its version 5) because with size_of_ptr==4 an array of 64kB could hold 16384 pointers to rows, but anyways, it wasn't). In general, addressing a spreadsheet position is done using unsigned short type variables for column, row, sheet (AKA table). Theoretically this would allow 65536 rows to be addressed, but at some places there are short type variables used where relative addressing is needed, for example in cell references. Some special values like USHRT_MAX or MAXROW+1 are used to denote an invalid row position, and furthermore the number of rows has to be dividable by a reasonable number producing a whole-numbered result which is necessary for the mechanism of broadcasting changes in areas where formulas are listening to. Hence the change from 16384 to 32000 instead of 32768.
Roughly said, a spreadsheet document may consist of up to 256 sheets, each sheet having 256 columns with each column containing a dynamic array with elements containing the row number and a pointer to the cell for a given row. Empty cells are not stored. The array is binary searchable and for evenly distributed filled columns an interpolating search is used. A similar array holds the cell style attributes (font, alignment, number format and so on) with each entry specifying an end row for that attribute, thus formatting an entire column with identical attributes results in only one entry.
There are a lot of
class ScDocument methods (see
accessing a cell position by
MethodName( USHORT nCol, USHORT
nRow, USHORT nTab );
where at least the nRow parameter will have to be changed to long, but it should be evaluated if all methods taking separated col/row/tab parameters couldn't be changed to take one
ScAddress (see below)
parameter instead. Similar, the
class ScTable methods
nCol, USHORT nRow );
USHORT nRow );and the
USHORT nRow );
row parameters have to be changed, also all
MethodName( ..., USHORT nStartRow,
nEndRow, ... );
of all of those classes.
Search( USHORT nRow, short& nIndex );
ScAttrArray and similar are
special in a way that the
short& nIndex reference is
used to return a position within an array where the position may at
most be the number of rows used. This of course has to be changed as
class ScAddress (see
contains column/row/table values encoded into one UINT32
value such that the row value occupies 16 bit and column and table
values each occupy 8 bit. Changing these would also affect the old
binary file format, so appropriate conversion methods would have to
be provided. It should be evaluated how a packing of information into
any whatsoever sized variable space could be accomplished, since an
ScAddress is quite often stored in memory. For example,
one INT32 may hold the row value and column and sheet
positions may be stored in INT16 values each. INT16
because at least the sheet number shouldn't be limited to 256 anymore
(this as a side effect of all the row limit changes, though a change
of the real sheet accessing methods would have to be carried out in a
A cell reference (
struct SingleRefData and
source/core/tool/refdata.cxx) in a formula contains an
absolute position and an relative position. Both values are INT16
values. If those are to be changed it should be thought over if it
would be really necessary to keep both the absolute value and the
relative value or if it wouldn't be sufficient to keep either one
(which of course would imply some changes in the
source/core/tool/compiler.cxx position accessing
methods). This would save a significant amount of memory if a lot of
references were used in a lot of formulas (which usually is the
There is also a
class ScTripel which partly
implements features found in
class ScAddress, and a
class ScRefTripel which is similar to the
with the exception that it is never used in formula data and has
slightly different capabilities. Both, ScTripel and ScRefTripel (see
are leftovers from prior versions and should be replaced by
and a new (to be created)
respectively throughout the entire application.
List of structs and classes having an USHORT (or short or UINT16 or INT16) row value as member variable
Note: this list was created in 2001 and is incomplete [2004-01-26]
UINT32 nAddress; encoded row in lower 16 bit
nRow; the end row of the range spanned by the attribute
nCount; number of used ScAttrEntry entries (max: number of used rows)
nLimit; number of allocated entries (ditto)
short nPos; holds the index position to a ScAttrArray element obtained by ScAttrArray::Search()
nCount; number of used ColEntry entries (max: number of used rows)
nLimit; number of allocated entries (ditto)
NOTE: Replace usage of ScTripel with ScAddress and delete ScTripel code. Delete ScTripel conversion code from ScAddress.
nCount; number of used ScMarkEntry entries (max: number of used rows)
nLimit; number of allocated entries (ditto)
short nRowCount; a count which in program flow may not exceed a value of 8. Just a nice trap for a grep.
This class is some old stuff almost not needed anymore, was used for the old ... (pssst, we can't use the word here since it is a registered trademark, guess by whom) what is called DataPilot in our application. The class is only used for import/export of the old binary file format.
NOTE: Calc 1.0 import filter, there shouldn't be any changes necessary.
#define MAXROW 31999
#define BCA_BRDCST_ALWAYS ScAddress( 0, 32767, 0 )
A special address (outside the normal valid address range) used to signal an “always changed” function or cell.
#define ASCIIDLG_MAXROWS 32000
The maximum number of rows displayed in the ASCII import preview dialog. It is questionable if this should be increased since arrays for holding the imported data are created.
NumericField ED_ROW: Maximum = 32000; Last = 32000;The navigator resource defines an upper limit for the row edit field and its spin button.
A couple of iterators (see
source/core/data/dociter.cxx) make direct use of
internal data structures like those of
ScAttrArray using row values.
Reference updating methods like those of
make extensive use of USHORT and short
variables and the MAXROW limit.
Each sheet contains two arrays,
pRowFlags (see inc/table.hxx and source/core/data/table1.cxx),
sized MAXROW+1 each. If the number of rows is to be
increased significantly a new mechanism would have to be implemented
since keeping those row infos for a million rows or so isn't
desirable. Even now these two arrays allocate about 90kB per sheet.
class ScBroadcastAreaSlot (see
source/core/data/bcaslot.cxx) makes use of an upper row
limit in the way that the rows are distributed over a number of
slots. The number of slots is related to the number of rows.
class ScChangeTrack uses a similar technique to
combine positions into slot buckets for faster access.
Currently, both algorithms of
ScChangeTrack can't work with an arbitrary changing row
limit, they do need a fixed upper limit set at compile time. Both
algorithms would also not work very well (regarding speed, memory
footprint and efficiency) if the upper limit would be too high.
source/core/tool/chartarr.cxx) creates a temporary array
which may become as big as the spanning area of a (multi-) selection.
Currently the maximum limit this implies is 8MB (256 columns x 32000
rows), this will automatically grow if more rows are available and
the user spans a selection from upper left to lower right. However,
the upcoming future chart implementation will not need this mechanism
anymore, but we'll have to keep it for backwards compatibility.
The drawing layer is not directly related to the row limit, but the area it covers is of course determined by the number of available rows.
It would be challenging to offer an almost unlimited number of rows, say a million or two or hundred (if your system had that much memory). However, before that could be accomplished the above mentioned mechanisms of the drawing layer needed to be changed and row flags, ScBroadcastAreaSlot and ScChangeTrack needed to be changed to be less memory consuming.
Therefor the changes should be carried out in several steps:
Change all variables used for row numbers from USHORT and short to INT32 using a
SCROWtypedef. This includes any changes needed or type conversion in import/export filter, and to compensate for any side effect that might occur. The change should be carried out successively instead of in one big move in order to maintain a usable application and not to render it useless for weeks. To help in finding all necessary places a special access operators and methods converter class
SCROWshould be used that forces the compiler to throw error diagnostics whenever an USHORT or short is used in combination with
SCROW. A similar class is already available (on the writer's machine ;-) and just needs some modification.
Find a solution for the memory footprint problem of the
pRowFlagsarrays. Similar to the mechanism used to manage row entries of a column array of used rows, dynamic arrays of applied row heights and flags should be maintained.
For MS-Excel compatibility increase the limit to 64k rows. It should still be ok to use the same drawing layer and
ScChangeTrackmechanisms at this stage, even if the latter two would result in some more memory consumption, but those are on a per document basis and not a per sheet basis.
At this point, a version may be released to provide an interim solution for those who need it, for example for extended MS-Excel compatibility.
Find solutions for the
ScChangeTrackproblems which have to be really scalable. The first might involve a complete redesign of the broadcaster/listener concept of formula cells, a heavy change! But it would be necessary anyways, because there are some performance issues with it.
Wait for a reimplementation of the drawing layer (which will come) and use that because it will do away some quirks related to anchor positions, different map modes, rounding errors, and the area covered.
Finally set an arbitrary row limit. Or don't have an arbitrary limit at all?
Since we'll never touch the binary file format again in the sense of modifying anything of it's structure to store new features, and the fact that we're working on a method to strip the binary filters from the core code and have separate filters to convert SO5 file format to XML file format, we won't have to care about the binary file stream operators or code accessing file streams if we wait for the new filter code to be functional before touching the binary file format code. This will ease things a lot. A second mile stone we want to achieve before carrying out massive changes on the source code are the accessibility and CTL changes for the next release that are going on in the 642 builds. Both changes are expected to be finished by the end of July. The following table uses week x for the availability of the filter and main feature completeness on accessibility and CTL, and references to week x+1 and so on. For calculating the duration of tasks it is assumed that a week has about 2.5 developer's days, not counting time needed for other tasks such as fixing bugs, code reviews, and participating in mailing lists, meetings and conference calls. Time lines of best case – worst case are given, this includes assumptions of best case getting help when appropriate and worst case when I'd to do everything on my own. Vacations not included.
NOTE: Previous versions of this document stated a "starting date" of August 2002, based on the assumption that OOo1.1/SO6.1 were feature complete and that the binary filters were stripped until end of July. Unfortunately that wasn't the case, and people kept asking me about the progress and why this task wasn't even started. At the moment I cannot (and I don't want to) give yet another estimate of things that aren't even the slightest bit under my control to be nailed down on it. So I just state that waiting for other tasks is ongoing, without giving any due date.
NOTE2: Started in week 48 of 2003 without waiting for the binary filter to be stripped. Based on the 2.5 days per week calculation and including 2 weeks holidays the approximated end date will be between April and June of 2004.
Breaking the limit
To be done.