Author: Eike
Rathke
Document state:
TODO:
Last
changed:
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
inc/document.hxx
and source/data/documen*.cxx
accessing a cell position byMethodName( 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
(see inc/table.hxx
and
source/core/data/table*.cxx
)MethodName( USHORT
nCol, USHORT nRow );
and the class ScColumn
methods (see inc/column.hxx
and
source/core/data/column*.cxx
)MethodName(
USHORT nRow );
and the
methods (see class ScAttrArray
and
inc/attarray.hxx
)source/core/data/
attarray
.cxxMethodName(
USHORT nRow );
row parameters have to be changed,
also allMethodName( ..., USHORT nStartRow,
USHORT
nEndRow, ...
);
of all of those
classes.Search( USHORT nRow, short& nIndex );
of
ScColumn
and 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
well.
Additionally, a class ScAddress
(see
inc/global.hxx
and source/core/data/global2.cxx
)
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
second step).
A cell reference (struct SingleRefData
and struct
ComplRefData
, see inc/refdata.hxx
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 class
ScInterpreter
(see source/core/inc/interpre.hxx
and source/core/tool/interpr*.cxx
) and class
ScCompiler
(see inc/compiler.hxx
and
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
case).
There is also a class ScTripel
which partly
implements features found in class ScAddress
, and a
class ScRefTripel
which is similar to the SingleRefData
with the exception that it is never used in formula data and has
slightly different capabilities. Both, ScTripel and ScRefTripel (see
inc/global.hxx
and source/core/data/global.cxx
),
are leftovers from prior versions and should be replaced by ScAddress
and a new (to be created) class ScRefAddress
respectively throughout the entire application.
class ScAddress
UINT32 nAddress; encoded row in lower 16
bit
struct ScAttrEntry
nRow; the end row of the range spanned
by the attribute
class ScAttrArray
nCount; number of used ScAttrEntry
entries (max: number of used rows)
nLimit; number of allocated
entries (ditto)
class ScAttrIterator
short nPos; holds the index position
to a ScAttrArray element obtained by ScAttrArray::Search()
nRow;
nEndRow;
class ScMergeAttr
INT16 nRowMerge;
class ScFormulaCell
nMatRows;
class ScChartPositionMap
nRowCount;
class ScChartArray
nStartRow;
class ScChangeTrack
nContentRowsPerSlot;
nContentSlots;
struct ColEntry
nRow;
class ScColumn
nCount; number of used ColEntry entries
(max: number of used rows)
nLimit; number of allocated entries
(ditto)
struct ScReferenceEntry
nRow;
class ScConsData
nRowCount;
class
ScDBData
nStartRow;
nEndRow;
nSortDestRow;
nQueryDestRow;
class ScDocumentIterator
nRow;
class
ScValueIterator
nStartRow;
nEndRow;
nRow;
nColRow;
nNextRow;
nAttrEndRow;
class ScQueryValueIterator
nRow;
nColRow;
nAttrEndRow;
class ScCellIterator
nStartRow;
nEndRow;
nRow;
nColRow;
class ScQueryCellIterator
nRow;
nColRow;
nAttrEndRow;
class ScDocAttrIterator
nStartRow;
nEndRow;
class ScAttrRectIterator
nStartRow;
nEndRow;
class ScHorizontalCellIterator
nEndRow;
USHORT*
pNextRows;
nRow;
class ScHorizontalAttrIterator
nStartRow;
nEndRow;
USHORT*
pNextEnd;
nRow;
class
ScUsedAreaIterator
nNextRow;
nCellRow;
nAttrRow;
nFoundRow;
struct RowInfo
nRowNo;
struct ScSymbolStringCellEntry
nRow;
class ScDocument
nSrcMaxRow;
class ScTableRowsObj
nStartRow;
nEndRow;
class
ScDPOutput
nTabStartRow;
nMemberStartRow;
nDataStartRow;
nTabEndRow;
class ScDPSaveData
nRowGrandMode;
struct ScDPTableIteratorParam
nRowCount;
class ScEditUtil
nRow;
struct ScImportParam
nRow1;
nRow2;
class ScTripel
nRow;
NOTE: Replace usage of ScTripel
with ScAddress and delete ScTripel code. Delete ScTripel conversion
code from ScAddress.
struct ScQueryParam
nRow1;
nRow2;
nDestRow;
struct ScSubTotalParam
nRow1;
nRow2;
struct ScConsolidateParam
nRow;
struct ScPivotParam
nRow;
nRowCount;
struct ScMarkEntry
nRow;
class ScMarkArray
nCount; number of used ScMarkEntry
entries (max: number of used rows)
nLimit; number of allocated
entries (ditto)
class
ScPivot
nSrcRow1;
nSrcRow2;
nDestRow1;
nDestRow2;
nDataStartRow;
short
nRowCount; a count which in program flow may not exceed a value of
8. Just a nice trap for a grep.
short
nDataRowCount;
nRowIndex;
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.
class ScArea
nRowStart;
nRowEnd;
struct SingleRefData
INT16 nRow;
INT16 nRelRow;
struct ScExtTabOptions
UINT16 nTopRow;
UINT16
nTopSplitRow;
class ScExtDocOptions
UINT16 nCurRow;
struct ScSortParam
nRow1;
nRow2;
nDestRow;
class ScMatrix
nAnzRow;
struct ScEEParseEntry
nRow;
nRowOverlap;
class ScEEParser
nRowCnt;
nRowMax;
class
XclExpTableOp
nFirstRow;
nLastRow;
nColInpRow;
nRowInpCol;
nRowInpRow;
struct ScHTMLTableStackEntry
nRowCnt;
struct ScHTMLAdjustStackEntry
nNextRow;
nCurRow;
class ScHTMLTableData
nFirstRow;
nLastRow;
nRowSpan;
nDocRow;
struct Sc10ColData
Row;
NOTE: Calc 1.0 import filter,
there shouldn't be any changes necessary.
class XclExpCachedValueList
nRows;
class XclImpChart_LinkedData
nMinRowVal;
class ScMyNotEmptyCellsIterator
sal_uInt16 nCellRow;
class ScRedlinData
nRow;
class ScDataGrid
nNumberOfRows;
class ScGridWindow
nFilterBoxRow;
class ScNavigatorDlg
nCurRow;
class ScOutputData
nEditRow;
struct ScPrintState
nStartRow;
nEndRow;
class ScPageRowEntry
nStartRow;
nEndRow;
class
ScPrintFunc
nRepeatStartRow;
nRepeatEndRow;
nStartRow;
nEndRow;
class ScSpellingEngine
nOrgRow;
nOldRow;
class ScTabPageSortFields
nFirstRow;
class ScUndoCursorAttr
nRow;
class ScUndoEnterData
nRow;
class ScUndoPageBreak
nRow;
class ScUndoThesaurus
nRow;
class ScUndoSubTotals
nNewEndRow;
class ScUndoImportData
nEndRow;
class ScUndoRepeatDB
nNewEndRow;
class ScViewData
nEditRow;
nEditEndRow;
#define MAXROW 31999
inc/global.hxx
THE
limit.
#define BCA_BRDCST_ALWAYS ScAddress( 0, 32767, 0
)
inc/global.hxx
A special address (outside the normal
valid address range) used to signal an “always changed”
function or cell.
#define ASCIIDLG_MAXROWS
32000
source/ui/dbgui/asciiopt.cxx
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.source/ui/navipi/navipi.src
, Window
RID_SCDLG_NAVIGATOR
A couple of iterators (see inc/dociter.hxx
and
source/core/data/dociter.cxx
) make direct use of
internal data structures like those of ScColumn
and
ScAttrArray
using row values.
Reference updating methods like those of class ScRefUpdate
(see inc/refupdat.hxx
and source/core/tool/refupdat.cxx
)
make extensive use of USHORT and short
variables and the MAXROW limit.
Each sheet contains two arrays, pRowHeight
and
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 ScBroadcastAreaSlot
and
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.
ScChartArray::GlueState()
(see
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 SCROW
typedef. 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 SCROW
should 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
pRowHeight
and pRowFlags
arrays. 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
ScBroadcastAreaSlot
and ScChangeTrack
mechanisms 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 ScBroadcastAreaSlot
and
ScChangeTrack
problems 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.
To be done.