Oups I just notice a Cut&Paste problem. The prototype I am proposing is
as follow, sorry about that. Optionnally, insert could return a
reference or a pointer to the newly inserted paragraph but I think that
the get(size_t) function is cleaner.
class ParagraphList
{
public:
///
typedef std::list<Paragraph>::iterator Pli;
typedef std::list<Paragraph>::const_iterator Iter;
protected:
typedef std::vector<Pli>::iterator Iter;
list<Paragraph> ParList_;
vector<Pli> PliVector_;
public:
///
ParagraphList()
{
// Reserve Memory for 100000 iterators
// which would represent 1000000 paragraph
// I guess this is enough?
PliVector_.reserve(100000);
}
Paragrah& get(size_t pos)
{
BOOST_ASSERT(pos < PliVector_.size())
return *PliVector_[pos];
}
/// Erases the paragraph at position pos.
bool erase(size_t pos)
{
if (pos >= PliVector_.size())
{
// What happened here?
return false
}
size_t new_size=PliVector_.size()-1;
PliVector.resize(new_size);
if (pos == PliVector_.size())
{
PliVector[pos] = ParList_.pop_back(Par);
}
else
{
ParList_.erase(PliVector_[pos]);
}
// Warning: I think Vector resize does not keep data
// in this case. So it is safer to update the vector
// entirely
Pli pli = ParList_.begin();
for (size_t i=0; i<new_size; ++i)
{
PliVector[i]=pli
++pli;
}
return true;
}
/// Inserts the paragraph par at position pos.
/// The subsequent paragraph are shifted toward the end.
bool insert(size_t pos, const Paragraph& par)
{
if (pos > PliVector_.size())
{
// What happened here?
return false;
}
size_t new_size=PliVector_.size()+1;
PliVector.resize(new_size);
if (pos == PliVector_.size())
{
PliVector[pos] = ParList_.push_back(Par);
}
else
{
Pli pli = ParList_.insert(PliVector_[pos], Par);
for (size_t i=pos; i<new_sizepli; ++i)
{
PliVector[i]=pli
++pli;
}
}
return true;
}
};
Abdel a écrit :
Martin Vermeer a écrit :
On Tue, Jan 03, 2006 at 07:52:13PM +0100, Abdel wrote:
Hello,
On windows with 1.4.0cvs on for big documents (ex: Extended.lyx),
there is a big delay (~1s) before a "Carriage Return" is shown on
screen after typing the "enter" key in the middle of a paragraph. The
same will happen when you type "Backspace" at the beginning of a
paragraph. On the contrary, if you type Ctrl-Z immediately after, the
screen update is instantaneous.
For both keys, 1.3.7pre is very quick.
I am trying to investigate if I could speed-up this a bit because
this is very, very irritating. I found that the big delay is in
"LyXText::breakParagraph" and more precisely in "::breakParagraph",
paragraph_funcs.C:97. The time consuming operation is the insertion
of a new paragraph inside the ParagraphList which is in fact a
std::vector :
ParagraphList::iterator tmp =
pars.insert(pars.begin() + par_offset + 1, Paragraph());
I have compiled this file with -O3 but the slowness is still there.
Indeed insertion inside a vector is known to be inefficient. I have
read the history about ParagraphList_fwd.h
(http://www.lyx.org/cgi-bin/viewcvs.cgi/lyx-devel/src/ParagraphList_fwd.h)
and I guess there might be some valid reason to choose a vector
instead of a list but performance wise, it shows, definitely. I have
tried to replace with a list but this won't compile because some
source needs the [] operator. I have also tried a deque and the
results are a bit better. The weird thing is that the slowness is not
at the same place. Indeed, within a "Standard" environment, the
paragraph insertion at the beginning seems to be very fast but the
following operation is slowing things down:
for (pos_type i = pos_end; i >= pos; --i)
par.eraseIntern(i);
Within a "List" environment, the behavior is the same as with a
vector based class: the slowness is in the paragraph insertion at the
beginning.
But I don't know if this is safe, so my question is: is there any
assumption in the code that the ParagraphList use a contiguous
memory? Deque does not... But "Extended.lyx" loads fine and all seems
correct (math, table, etc...).
There is a pending patch which could use the <vector> property... or
not (bug 2015) ;-)
From what I see it uses size() and operator[] so deque would be fine
here also. But maybe rewriting this patch to use ParagraphList::iterator
and algorithm::find would be better, wouldn't it? This way we won't rely
on vector property.
I think a better solution would be to use a map or maybe a vector of
pointer.
Like it is now, IMHO, lyx-1.4 is close to unusable under window. Is
there some unofficial patch that would speed up things a bit?
Andre had something that IIRC would replace the official insert() by a
homegrown one, presumably faster. (What's the status of that?)
I think it is possible to rewrite the ParagraphList class that would not
need the removal of the official insert(), only a cosmetic change.
IMHO, a good solution would be to use a list<Paragraph> member to store
the paragraphs and a vector<list<Paragraph>::iterator> for the
interface. This way ParagraphList::insert would call list::insert and
then update the vector or list iterator. I believe this would imply
minimal change to the code using ParagraphList; we would just need to
replace "insert(XXX.begin()+pos, Par)" with "insert(pos, Par)". Here is
a class prototype (not tested):
class ParagraphList
{
public:
///
typedef std::vector <Paragraph*> BaseType;
typedef std::vector <Paragraph*>::iterator Iter;
typedef std::vector <Paragraph*>::const_iterator ConstIter;
typedef std::list<Paragraph>::iterator Pli;
typedef std::list<Paragraph>::const_iterator Iter;
protected:
typedef std::vector<Pli>::iterator Iter;
list<Paragraph> ParList_;
vector<Pli> PliVector_;
public:
///
ParagraphList()
{
// Reserve Memory for 100000 iterators
// which would represent 1000000 paragraph
// I guess this is enough?
PliVector_.reserve(100000);
}
Paragrah& get(size_t pos)
{
BOOST_ASSERT(pos < PliVector_.size())
return *PliVector_[pos];
}
/// Erases the paragraph at position pos.
bool erase(size_t pos)
{
if (pos >= PliVector_.size())
{
// What happened here?
return false
}
size_t new_size=PliVector_.size()-1;
PliVector.resize(new_size);
if (pos == PliVector_.size())
{
PliVector[pos] = ParList_.pop_back(Par);
}
else
{
ParList_.erase(PliVector_[pos]);
}
// Warning: I think Vector resize does not keep data
// in this case. So it is safer to update the vector
// entirely
Pli pli = ParList_.begin();
for (size_t i=0; i<new_size; ++i)
{
PliVector[i]=pli
++pli;
}
return true;
}
};
What do think?
Abdel.
Thanks,
Abdel.
- Martin
