Opened 10 years ago

Closed 10 years ago

#475 closed task (fixed)

Store data in sparse container

Reported by: Peter Johansson Owned by: Peter Johansson
Priority: major Milestone: svndigest 0.9
Component: core Version: trunk
Keywords: Cc:

Description (last modified by Peter Johansson)

Daughter of ticket #296

Currently, data are stored in vectors such that vec[rev] gives the stats for revision rev. For most revisions the stats is the same as what it was for previous revision, because the file was not modified in that revision. Therefore one could perhaps save some memory by holding the stats in a map<rev, count> instead. But there is typically more overhead in a map than in a vector, so how much is the gain? Also, for high level Nodes such as the Root Directory, the stats are typically not sparse and there is no gain.

Some features of the class:

const int& operator[](rev) const
int& operator[](rev)
size() const

vec[0] should always be 0.

In addition it probably good to have an iterator that iterates through elements where the value changes (could likely be underlying map::iterator). Using that one could draw fewer lines in the plotting by only draw lines when count/value changes.

Change History (14)

comment:1 Changed 10 years ago by Peter Johansson

Description: modified (diff)

comment:2 Changed 10 years ago by Peter Johansson

Status: newassigned
Summary: Store data in parse containerStore data in sparse container

comment:3 Changed 10 years ago by Peter Johansson

Looking at how the vectors are used, it turns out that we need two types of vector. 1) Traditional sparse vector in which we only store non-zero values and 2) A vector which is sort of the accumulated sum (integral) of 1, i.e., we only store values different from previous revision. We need to be able to create 2) from 1) which should be easy to implement. The two vectors are very similar so I think I create a common base class, or is a template/policy preferable?

comment:4 Changed 10 years ago by Peter Johansson

(In [1187]) new Vector class. refs #475

comment:5 Changed 10 years ago by Peter Johansson

(In [1189]) reverting part of r1188 that should wait until Vector class is implemented (refs #475).

comment:6 Changed 10 years ago by Peter Johansson

(In [1194]) refs #475. First version using Sparse Vector class. This change is obviously quite invasive and thus the size of this commit is larger than what is preferred. I've tried to limit as much as possible and left optimization and style issues behind with a note 'FIXME'.

comment:7 Changed 10 years ago by Peter Johansson

(In [1195]) refs #475, erase elements in underlying map (when possible) when resizing Vector.

comment:8 Changed 10 years ago by Peter Johansson

(In [1196]) speeding up Vector::back(). refs #475

comment:9 Changed 10 years ago by Peter Johansson

(In [1198]) plot stairs only when count changes in a revision. refs #475

comment:10 Changed 10 years ago by Peter Johansson

(In [1201]) prefer operator+= rather than operator+. refs #475

comment:11 Changed 10 years ago by Peter Johansson

(In [1203]) refs #475. prefer operator+= and remove operator+ for Vector class to ensure we use +=

comment:12 Changed 10 years ago by Peter Johansson

(In [1204]) refs #475. remove dead code

comment:13 Changed 10 years ago by Peter Johansson

(In [1208]) Changed value type of SparseVector? to be (signed) int. Use Vector::iterator when printing Vector's data instead of using operator[] refs #475

comment:14 Changed 10 years ago by Peter Johansson

Resolution: fixed
Status: assignedclosed

(In [1209]) remove FIXME that would just make the already complicated code unreadable. closes #475

Note: See TracTickets for help on using tickets.