Re: Insets Data Structure (was: Re: 20% speedup of paragraph redraw with simple patch)
Dov Feldstern wrote: Why do we need that structure at all? Given that our char_type is 32-bits, and we don't use all 32, we could do something like the following: the insets themselves could be stored in a hash table, without storing their positions in that structure. At each position in the paragraph where an inset appears, instead of just the META_INSET character, we store an actual key into the hash table. (From the comment on META_INSET I understand that we don't use any values above 0x20001 --- which means that we have more than enough room for keys to as many insets as we'd like in a single paragraph...). Then, there's no need of keeping the insets structure in sync with the paragraph itself after every insertion... Note that if anything, this will make faster insertion and deletions, not lookups (the potential bottleneck that started this thread). I doubt that it has a real impact. Second point, I think a hash table is really not good because then iteration *in order* over insets of a paragraph becomes much worse than now (I think we use it in a few places). Now for a change, how about focusing on real bottlenecks? SCNR ;-) A/
Re: Insets Data Structure (was: Re: 20% speedup of paragraph redraw with simple patch)
On Mon, Jun 18, 2007 at 10:41:54PM +0200, Alfredo Braunstein wrote: Dov Feldstern wrote: Why do we need that structure at all? Given that our char_type is 32-bits, and we don't use all 32, we could do something like the following: the insets themselves could be stored in a hash table, without storing their positions in that structure. At each position in the paragraph where an inset appears, instead of just the META_INSET character, we store an actual key into the hash table. (From the comment on META_INSET I understand that we don't use any values above 0x20001 --- which means that we have more than enough room for keys to as many insets as we'd like in a single paragraph...). Then, there's no need of keeping the insets structure in sync with the paragraph itself after every insertion... Note that if anything, this will make faster insertion and deletions, not lookups (the potential bottleneck that started this thread). I doubt that it has a real impact. Second point, I think a hash table is really not good because then iteration *in order* over insets of a paragraph becomes much worse than now (I think we use it in a few places). Now for a change, how about focusing on real bottlenecks? SCNR ;-) Like the build process? ;-} Andre'
Re: Insets Data Structure (was: Re: 20% speedup of paragraph redraw with simple patch)
Dov Feldstern wrote: > Why do we need that structure at all? Given that our char_type is > 32-bits, and we don't use all 32, we could do something like the > following: the insets themselves could be stored in a hash table, > without storing their positions in that structure. At each position in > the paragraph where an inset appears, instead of just the META_INSET > character, we store an actual key into the hash table. (From the comment > on META_INSET I understand that we don't use any values above 0x20001 > --- which means that we have more than enough room for keys to as many > insets as we'd like in a single paragraph...). Then, there's no need of > keeping the insets structure in sync with the paragraph itself after > every insertion... Note that if anything, this will make faster insertion and deletions, not lookups (the potential bottleneck that started this thread). I doubt that it has a real impact. Second point, I think a hash table is really not good because then iteration *in order* over insets of a paragraph becomes much worse than now (I think we use it in a few places). Now for a change, how about focusing on real bottlenecks? SCNR ;-) A/
Re: Insets Data Structure (was: Re: 20% speedup of paragraph redraw with simple patch)
On Mon, Jun 18, 2007 at 10:41:54PM +0200, Alfredo Braunstein wrote: > Dov Feldstern wrote: > > > Why do we need that structure at all? Given that our char_type is > > 32-bits, and we don't use all 32, we could do something like the > > following: the insets themselves could be stored in a hash table, > > without storing their positions in that structure. At each position in > > the paragraph where an inset appears, instead of just the META_INSET > > character, we store an actual key into the hash table. (From the comment > > on META_INSET I understand that we don't use any values above 0x20001 > > --- which means that we have more than enough room for keys to as many > > insets as we'd like in a single paragraph...). Then, there's no need of > > keeping the insets structure in sync with the paragraph itself after > > every insertion... > > Note that if anything, this will make faster insertion and deletions, not > lookups (the potential bottleneck that started this thread). I doubt that > it has a real impact. > > Second point, I think a hash table is really not good because then iteration > *in order* over insets of a paragraph becomes much worse than now (I think > we use it in a few places). > > Now for a change, how about focusing on real bottlenecks? SCNR ;-) Like the build process? ;-} Andre'
Insets Data Structure (was: Re: 20% speedup of paragraph redraw with simple patch)
Jean-Marc Lasgouttes wrote: Dov == Dov Feldstern [EMAIL PROTECTED] writes: Dov Hmm, I just came across this yesterday when trying to figure out Dov what was going on with bug 3011, and wondered about it. I'm not Dov sure if this is what you mean or not, but it might be relevant... Dov http://www.lyx.org/trac/browser/lyx-devel/trunk/src/Paragraph.cpp?rev=18599#L446 Yes, what I mean is that in this case we would have to recreate the structure instead of update it. I do not know how costly it is but Abdel is confident that it is not a problem. JMarc Why do we need that structure at all? Given that our char_type is 32-bits, and we don't use all 32, we could do something like the following: the insets themselves could be stored in a hash table, without storing their positions in that structure. At each position in the paragraph where an inset appears, instead of just the META_INSET character, we store an actual key into the hash table. (From the comment on META_INSET I understand that we don't use any values above 0x20001 --- which means that we have more than enough room for keys to as many insets as we'd like in a single paragraph...). Then, there's no need of keeping the insets structure in sync with the paragraph itself after every insertion...
Insets Data Structure (was: Re: 20% speedup of paragraph redraw with simple patch)
Jean-Marc Lasgouttes wrote: "Dov" == Dov Feldstern <[EMAIL PROTECTED]> writes: Dov> Hmm, I just came across this yesterday when trying to figure out Dov> what was going on with bug 3011, and wondered about it. I'm not Dov> sure if this is what you mean or not, but it might be relevant... Dov> http://www.lyx.org/trac/browser/lyx-devel/trunk/src/Paragraph.cpp?rev=18599#L446 Yes, what I mean is that in this case we would have to recreate the structure instead of update it. I do not know how costly it is but Abdel is confident that it is not a problem. JMarc Why do we need that structure at all? Given that our char_type is 32-bits, and we don't use all 32, we could do something like the following: the insets themselves could be stored in a hash table, without storing their positions in that structure. At each position in the paragraph where an inset appears, instead of just the META_INSET character, we store an actual key into the hash table. (From the comment on META_INSET I understand that we don't use any values above 0x20001 --- which means that we have more than enough room for keys to as many insets as we'd like in a single paragraph...). Then, there's no need of keeping the insets structure in sync with the paragraph itself after every insertion...
Re: 20% speedup of paragraph redraw with simple patch
Andre Poenitz wrote: On Thu, Jun 14, 2007 at 05:49:53PM +0200, Abdelrazak Younes wrote: Moreover, it remains to be seen whether the map is faster in the cases where the container typically has at most 10 elements. It might be that a stupid plain loop is faster... Maybe not faster but a lot cleaner. You may have noticed that users are complaining about speed, not on code cleanliness. When you quote something please quote the full sentence: Am I am pretty sure that it will make the cases similar to the one found by Stefan easier to optimize. I end this thread. Abdel.
Re: 20% speedup of paragraph redraw with simple patch
On Thu, Jun 14, 2007 at 09:01:49PM +0200, Andre Poenitz wrote: On Thu, Jun 14, 2007 at 05:05:32PM +0200, Stefan Schimanski wrote: I did some profiling of paragraph drawing. 20% of the whole time while inserting characters and redrawing the screen was taken by Paragraph::getInset calls, each for every character. This is stupid. See the patch below for a loop iterating over the insets of a paragraph instead. O(insetnumber) instead of O(charnumber * ln insetnumber). Stefan ... Good catch. Patch is fine with me. [And I continue hating that wide() business ;-}] Andre' Come and help rip it out from 1.6 in Bromarv... Abdel's idea is sound and perhaps that's what I should have done in the first place rather than this elaborate hack. - Martin
Re: 20% speedup of paragraph redraw with simple patch
Dov == Dov Feldstern [EMAIL PROTECTED] writes: Dov Hmm, I just came across this yesterday when trying to figure out Dov what was going on with bug 3011, and wondered about it. I'm not Dov sure if this is what you mean or not, but it might be relevant... Dov http://www.lyx.org/trac/browser/lyx-devel/trunk/src/Paragraph.cpp?rev=18599#L446 Yes, what I mean is that in this case we would have to recreate the structure instead of update it. I do not know how costly it is but Abdel is confident that it is not a problem. JMarc
Re: 20% speedup of paragraph redraw with simple patch
Andre Poenitz wrote: On Thu, Jun 14, 2007 at 05:49:53PM +0200, Abdelrazak Younes wrote: Moreover, it remains to be seen whether the map is faster in the cases where the container typically has at most 10 elements. It might be that a stupid plain loop is faster... Maybe not faster but a lot cleaner. You may have noticed that users are complaining about speed, not on code cleanliness. When you quote something please quote the full sentence: "Am I am pretty sure that it will make the cases similar to the one found by Stefan easier to optimize." I end this thread. Abdel.
Re: 20% speedup of paragraph redraw with simple patch
On Thu, Jun 14, 2007 at 09:01:49PM +0200, Andre Poenitz wrote: > On Thu, Jun 14, 2007 at 05:05:32PM +0200, Stefan Schimanski wrote: > > I did some profiling of paragraph drawing. 20% of the whole time > > while inserting characters and redrawing the screen was taken by > > Paragraph::getInset calls, each for every character. This is stupid. > > See the patch below for a loop iterating over the insets of a > > paragraph instead. O(insetnumber) instead of O(charnumber * ln > > insetnumber). > > > > Stefan > > ... > > Good catch. Patch is fine with me. > > [And I continue hating that wide() business ;-}] > > Andre' Come and help rip it out from 1.6 in Bromarv... Abdel's idea is sound and perhaps that's what I should have done in the first place rather than this elaborate hack. - Martin
Re: 20% speedup of paragraph redraw with simple patch
> "Dov" == Dov Feldstern <[EMAIL PROTECTED]> writes: Dov> Hmm, I just came across this yesterday when trying to figure out Dov> what was going on with bug 3011, and wondered about it. I'm not Dov> sure if this is what you mean or not, but it might be relevant... Dov> http://www.lyx.org/trac/browser/lyx-devel/trunk/src/Paragraph.cpp?rev=18599#L446 Yes, what I mean is that in this case we would have to recreate the structure instead of update it. I do not know how costly it is but Abdel is confident that it is not a problem. JMarc
20% speedup of paragraph redraw with simple patch
I did some profiling of paragraph drawing. 20% of the whole time
while inserting characters and redrawing the screen was taken by
Paragraph::getInset calls, each for every character. This is stupid.
See the patch below for a loop iterating over the insets of a
paragraph instead. O(insetnumber) instead of O(charnumber * ln
insetnumber).
Stefan
Index: src/rowpainter.cpp
===
--- src/rowpainter.cpp (Revision 18765)
+++ src/rowpainter.cpp (Arbeitskopie)
@@ -958,10 +958,11 @@
// done here.
// JSpitzm: We should aim at removing wide() altogether while
retaining
// typing speed within insets.
- for (pos_type i = rit-pos() ; i != rit-endpos(); ++i) {
- Inset const * const in = par.getInset(i);
- if (in) {
- InsetText * t = const_castInsetText
*(in-asTextInset());
+ InsetList::const_iterator iit = par.insetlist.insetIterator(rit-
pos());
+ InsetList::const_iterator iend = par.insetlist.end();
+ for (; iit != iend iit-pos rit-endpos(); ++iit) {
+ if (iit-inset) {
+ InsetText * t = const_castInsetText
*(iit-inset-asTextInset());
if (t)
t-setWide(in_inset_alone_on_row
leftEdgeFixed
parpaintinsetloop.patch
Description: Binary data
PGP.sig
Description: Signierter Teil der Nachricht
Re: 20% speedup of paragraph redraw with simple patch
Stefan == Stefan Schimanski [EMAIL PROTECTED] writes: Stefan I did some profiling of paragraph drawing. 20% of the whole Stefan time while inserting characters and redrawing the screen was Stefan taken by Paragraph::getInset calls, each for every character. Stefan This is stupid. See the patch below for a loop iterating over Stefan the insets of a paragraph instead. O(insetnumber) instead of Stefan O(charnumber * ln insetnumber). Very good catch. Did you find it with Shark.app? Profiling with tools like gprof does not contain the cost of the actual painting and gives too much importance to loops like above. Note also that the argument insetIterator(pos) probably has a cost too, and that it is not needed IMO. Since one is iterating over the whole paragraph, can't we keep the same InsetList::iterator all the time? It is nice to see how a drawing optimization makes the drawing slower... JMarc
Re: 20% speedup of paragraph redraw with simple patch
Am 14.06.2007 um 17:19 schrieb Jean-Marc Lasgouttes: Stefan == Stefan Schimanski [EMAIL PROTECTED] writes: Stefan I did some profiling of paragraph drawing. 20% of the whole Stefan time while inserting characters and redrawing the screen was Stefan taken by Paragraph::getInset calls, each for every character. Stefan This is stupid. See the patch below for a loop iterating over Stefan the insets of a paragraph instead. O(insetnumber) instead of Stefan O(charnumber * ln insetnumber). Very good catch. Did you find it with Shark.app? Profiling with tools like gprof does not contain the cost of the actual painting and gives too much importance to loops like above. Yes, shark. And still on the way. I think there are still plenty of those things. Note also that the argument insetIterator(pos) probably has a cost too, and that it is not needed IMO. Since one is iterating over the whole paragraph, can't we keep the same InsetList::iterator all the time? Sure we can. But it does not show up in the profile currently. Note that it is only done once per line. It is nice to see how a drawing optimization makes the drawing slower... Didn't look what the loop is actually doing. Interesting if really have been meant like that. Stefan JMarc PGP.sig Description: Signierter Teil der Nachricht
Re: 20% speedup of paragraph redraw with simple patch
Stefan Schimanski wrote:
I did some profiling of paragraph drawing. 20% of the whole time while
inserting characters and redrawing the screen was taken by
Paragraph::getInset calls, each for every character.
The whole time? Including screen drawing?
This is stupid. See
the patch below for a loop iterating over the insets of a paragraph
instead. O(insetnumber) instead of O(charnumber * ln insetnumber).
I am OK with it but maybe the real problem is why getInset is so slow?
Looking at InsetList::insetIterator(pos_type pos), this is no wonder really:
InsetList::iterator InsetList::insetIterator(pos_type pos)
{
InsetTable search_elem(pos, 0);
return lower_bound(list_.begin(), list_.end(), search_elem,
InsetTablePosLess());
}
InsetTable is basically 'pairpos, Inset*', so this InsetList is
basically reimplementing std::map in a less efficient way. Just
replacing the 'vectorInsetTable' with a 'mappos, Inset*' will clean
halves the code. And then you could just use the standard map iterator
anywhere it makes sense; and I bet there is a lot of case were it make
sense:
Find all getInset, Match case, Whole word, Subfolders, Find Results 1,
lyx-trunk, *.c;*.cpp;*.cxx;*.cc;*.tli;*.tlh;*.h;*.hpp;*.hxx;*.hh
D:\devel\lyx\trunk\src\CutAndPaste.cpp(195):
!pars[pit].insetAllowed(tmpbuf-getInset(i)-lyxCode()))
D:\devel\lyx\trunk\src\DocIterator.cpp(72): return
paragraph().isInset(pos()) ? paragraph().getInset(pos()) : 0;
D:\devel\lyx\trunk\src\DocIterator.cpp(89): return
paragraph().isInset(pos() - 1) ? paragraph().getInset(pos() - 1) : 0;
D:\devel\lyx\trunk\src\DocIterator.cpp(106): return
paragraph().isInset(pos() - 1) ? paragraph().getInset(pos() - 1) : 0;
D:\devel\lyx\trunk\src\DocIterator.cpp(331):n =
paragraph().getInset(tip.pos());
D:\devel\lyx\trunk\src\DocIterator.cpp(520): n =
paragraph().getInset(tip.pos());
D:\devel\lyx\trunk\src\DocIterator.cpp(597):inset =
cs.paragraph().getInset(cs.pos());
D:\devel\lyx\trunk\src\output_plaintext.cpp(211): int len =
par.getInset(i)-plaintext(buf, os, rp);
D:\devel\lyx\trunk\src\Paragraph.cpp(317):
owner_-getInset(pos)-setChange(change);
D:\devel\lyx\trunk\src\Paragraph.cpp(334):
owner_-getInset(pos)-setChange(change);
D:\devel\lyx\trunk\src\Paragraph.cpp(357):
owner_-getInset(pos)-acceptChanges(bparams);
D:\devel\lyx\trunk\src\Paragraph.cpp(366):
owner_-getInset(pos)-acceptChanges(bparams);
D:\devel\lyx\trunk\src\Paragraph.cpp(395):
owner_-getInset(pos)-rejectChanges(bparams);
D:\devel\lyx\trunk\src\Paragraph.cpp(681):
owner_-getInset(i)-plaintext(buf, os, runparams);
D:\devel\lyx\trunk\src\Paragraph.cpp(690): Inset * inset =
owner_-getInset(i);
D:\devel\lyx\trunk\src\Paragraph.cpp(1143): Inset const * inset =
getInset(i);
D:\devel\lyx\trunk\src\Paragraph.cpp(2180): Inset const * inset =
getInset(i);
D:\devel\lyx\trunk\src\Paragraph.cpp(2205): Inset const * inset =
getInset(i);
D:\devel\lyx\trunk\src\Paragraph.cpp(2223): Inset const * inset =
getInset(i);
D:\devel\lyx\trunk\src\Paragraph.cpp(2284): Inset const * inset =
getInset(i);
D:\devel\lyx\trunk\src\Paragraph.cpp(2311):
getInset(pos)-lyxCode() == Inset::NEWLINE_CODE;
D:\devel\lyx\trunk\src\Paragraph.cpp(2319): || (c ==
Paragraph::META_INSET getInset(pos)
D:\devel\lyx\trunk\src\Paragraph.cpp(2320):
getInset(pos)-isLineSeparator());
D:\devel\lyx\trunk\src\Paragraph.cpp(2328): return
getInset(pos)-isLetter();
D:\devel\lyx\trunk\src\Paragraph.cpp(2408):
getInset(i)-textString(buffer, os);
D:\devel\lyx\trunk\src\Paragraph.h(71): /// try getInset() and
crash. We should fix
D:\devel\lyx\trunk\src\Paragraph.h(314): Inset * getInset(pos_type pos) {
D:\devel\lyx\trunk\src\Paragraph.h(318): Inset const *
getInset(pos_type pos) const {
D:\devel\lyx\trunk\src\Paragraph.h(325):
getInset(pos)-lyxCode() == Inset::HFILL_CODE;
D:\devel\lyx\trunk\src\paragraph_funcs.cpp(40): if
(fromPar.getInset(fromPos)) {
D:\devel\lyx\trunk\src\rowpainter.cpp(182): Inset const * inset =
par_.getInset(pos);
D:\devel\lyx\trunk\src\rowpainter.cpp(422):
par_.getInset(pos)-descent());
D:\devel\lyx\trunk\src\rowpainter.cpp(787):
isHighlyEditableInset(par_.getInset(pos));
D:\devel\lyx\trunk\src\rowpainter.cpp(962): Inset const * const in
= par.getInset(i);
D:\devel\lyx\trunk\src\Text.cpp(385): return
par.getInset(pos)-width();
D:\devel\lyx\trunk\src\Text.cpp(566):
par.getInset(pos)-display())
D:\devel\lyx\trunk\src\Text2.cpp(315):
pars_[pit].getInset(pos)-noFontChange());
D:\devel\lyx\trunk\src\Text2.cpp(317): Inset * const inset =
pars_[pit].getInset(pos);
D:\devel\lyx\trunk\src\Text2.cpp(516):
pars_[pit].getInset(pos)-noFontChange())
D:\devel\lyx\trunk\src\Text2.cpp(927): Inset * insetBefore = pos?
pars_[pit].getInset(pos - 1): 0;
D:\devel\lyx\trunk\src\Text2.cpp(928): //Inset *
Re: 20% speedup of paragraph redraw with simple patch
Am 14.06.2007 um 17:27 schrieb Abdelrazak Younes:
Stefan Schimanski wrote:
I did some profiling of paragraph drawing. 20% of the whole time
while inserting characters and redrawing the screen was taken by
Paragraph::getInset calls, each for every character.
The whole time? Including screen drawing?
Yes, including everything. But using stdlib-debug I have to admit.
Compiling now without. I guess it is less problematic then.
This is stupid. See the patch below for a loop iterating over the
insets of a paragraph instead. O(insetnumber) instead of O
(charnumber * ln insetnumber).
I am OK with it but maybe the real problem is why getInset is so
slow? Looking at InsetList::insetIterator(pos_type pos), this is no
wonder really:
InsetList::iterator InsetList::insetIterator(pos_type pos)
{
InsetTable search_elem(pos, 0);
return lower_bound(list_.begin(), list_.end(), search_elem,
InsetTablePosLess());
}
InsetTable is basically 'pairpos, Inset*', so this InsetList is
basically reimplementing std::map in a less efficient way. Just
replacing the 'vectorInsetTable' with a 'mappos, Inset*' will
clean halves the code. And then you could just use the standard map
iterator anywhere it makes sense; and I bet there is a lot of case
were it make sense:
mapinsetlist.patch
Description: Binary data
Stefan
PGP.sig
Description: Signierter Teil der Nachricht
Re: 20% speedup of paragraph redraw with simple patch
Stefan Schimanski wrote: Am 14.06.2007 um 17:27 schrieb Abdelrazak Younes: Stefan Schimanski wrote: I did some profiling of paragraph drawing. 20% of the whole time while inserting characters and redrawing the screen was taken by Paragraph::getInset calls, each for every character. The whole time? Including screen drawing? Yes, including everything. But using stdlib-debug I have to admit. Compiling now without. I guess it is less problematic then. I am pretty sure it won't be that problematic then... too bad! ;-) Abdel.
Re: 20% speedup of paragraph redraw with simple patch
Abdelrazak Younes wrote:
I am OK with it but maybe the real problem is why getInset is so slow?
Looking at InsetList::insetIterator(pos_type pos), this is no wonder
really:
InsetList::iterator InsetList::insetIterator(pos_type pos)
{
InsetTable search_elem(pos, 0);
return lower_bound(list_.begin(), list_.end(), search_elem,
InsetTablePosLess());
}
InsetTable is basically 'pairpos, Inset*', so this InsetList is
basically reimplementing std::map in a less efficient way. Just
Are you sure it's less efficient? AFAICS this is O(ln n) just like std::map,
constants may vary (in one side or the other).
replacing the 'vectorInsetTable' with a 'mappos, Inset*' will clean
halves the code. And then you could just use the standard map iterator
anywhere it makes sense; and I bet there is a lot of case were it make
sense:
The code will be a bit cleaner maybe... but it is self-contained and clean
enough, and has been working flawlessly for ages... so be sure there is
really a gain if you are going to switch.
A/
Re: 20% speedup of paragraph redraw with simple patch
Stefan == Stefan Schimanski [EMAIL PROTECTED] writes: Stefan Yes, including everything. But using stdlib-debug I have to Stefan admit. Compiling now without. I guess it is less problematic Stefan then. Or maybe not problematic at all. stdlib is really very costly in terms of iterating over stl constructs. Profiling with it is kind of useless... InsetTable is basically 'pair', so this InsetList is basically reimplementing std::map in a less efficient way. Just replacing the 'vectorInsetTable' with a 'map' will clean halves the code. And then you could just use the standard map iterator anywhere it makes sense; and I bet there is a lot of case were it make sense: But this is not for now, right? Moreover, it remains to be seen whether the map is faster in the cases where the container typically has at most 10 elements. It might be that a stupid plain loop is faster... JMarc
Re: 20% speedup of paragraph redraw with simple patch
Jean-Marc Lasgouttes wrote: Stefan == Stefan Schimanski [EMAIL PROTECTED] writes: Stefan Yes, including everything. But using stdlib-debug I have to Stefan admit. Compiling now without. I guess it is less problematic Stefan then. Or maybe not problematic at all. stdlib is really very costly in terms of iterating over stl constructs. Profiling with it is kind of useless... InsetTable is basically 'pair', so this InsetList is basically reimplementing std::map in a less efficient way. Just replacing the 'vectorInsetTable' with a 'map' will clean halves the code. And then you could just use the standard map iterator anywhere it makes sense; and I bet there is a lot of case were it make sense: But this is not for now, right? Right. Moreover, it remains to be seen whether the map is faster in the cases where the container typically has at most 10 elements. It might be that a stupid plain loop is faster... Maybe not faster but a lot cleaner. Am I am pretty sure that it will make the cases similar to the one found by Stefan easier to optimize. Abdel.
Re: 20% speedup of paragraph redraw with simple patch
Alfredo Braunstein wrote:
Abdelrazak Younes wrote:
I am OK with it but maybe the real problem is why getInset is so slow?
Looking at InsetList::insetIterator(pos_type pos), this is no wonder
really:
InsetList::iterator InsetList::insetIterator(pos_type pos)
{
InsetTable search_elem(pos, 0);
return lower_bound(list_.begin(), list_.end(), search_elem,
InsetTablePosLess());
}
InsetTable is basically 'pairpos, Inset*', so this InsetList is
basically reimplementing std::map in a less efficient way. Just
Are you sure it's less efficient?
No, that was just a guess.
AFAICS this is O(ln n) just like std::map,
constants may vary (in one side or the other).
replacing the 'vectorInsetTable' with a 'mappos, Inset*' will clean
halves the code. And then you could just use the standard map iterator
anywhere it makes sense; and I bet there is a lot of case were it make
sense:
The code will be a bit cleaner maybe...
For sure ;-)
but it is self-contained and clean
enough, and has been working flawlessly for ages... so be sure there is
really a gain if you are going to switch.
I am not proposing to switch before 1.5.0 but I might implement it just
for fun and ask Stefan to try it out with Shark ;-)
Abdel.
Re: 20% speedup of paragraph redraw with simple patch
Abdelrazak Younes wrote:
Alfredo Braunstein wrote:
but it is self-contained and clean
enough, and has been working flawlessly for ages... so be sure there is
really a gain if you are going to switch.
I am not proposing to switch before 1.5.0 but I might implement it just
for fun and ask Stefan to try it out with Shark ;-)
Just for fun Stefan, could you try this out?
Abdel.
Index: InsetList.cpp
===
--- InsetList.cpp (revision 18766)
+++ InsetList.cpp (working copy)
@@ -24,25 +24,7 @@
namespace lyx {
using std::endl;
-using std::lower_bound;
-
-namespace {
-
-typedef InsetList::InsetTable Table;
-
-class InsetTablePosLess : public std::binary_functionTable, Table, bool {
-public:
- bool operator()(Table const t1, Table const t2) const
- {
- return t1.pos t2.pos;
- }
-};
-
-} // namespace anon
-
-
-
InsetList::~InsetList()
{
// If we begin storing a shared_ptr in the List
@@ -50,46 +32,39 @@
List::iterator it = list_.begin();
List::iterator end = list_.end();
for (; it != end; ++it) {
- delete it-inset;
+ delete it-second;
}
}
InsetList::iterator InsetList::insetIterator(pos_type pos)
{
- InsetTable search_elem(pos, 0);
- return lower_bound(list_.begin(), list_.end(), search_elem,
- InsetTablePosLess());
+ return list_.find(pos);
}
InsetList::const_iterator InsetList::insetIterator(pos_type pos) const
{
- InsetTable search_elem(pos, 0);
- return lower_bound(list_.begin(), list_.end(), search_elem,
- InsetTablePosLess());
+ return list_.find(pos);
}
void InsetList::insert(Inset * inset, pos_type pos)
{
- List::iterator end = list_.end();
- List::iterator it = insetIterator(pos);
- if (it != end it-pos == pos) {
+ List::iterator it = list_.find(pos);
+ if (it != list_.end())
lyxerr ERROR (InsetList::insert):
There is an inset in position: pos endl;
- } else {
- list_.insert(it, InsetTable(pos, inset));
- }
+ else
+ list_[pos] = inset;;
}
void InsetList::erase(pos_type pos)
{
- List::iterator end = list_.end();
- List::iterator it = insetIterator(pos);
- if (it != end it-pos == pos) {
- delete it-inset;
+ List::iterator it = list_.find(pos);
+ if (it != list_.end()) {
+ delete it-second;
list_.erase(it);
}
}
@@ -97,11 +72,10 @@
Inset * InsetList::release(pos_type pos)
{
- List::iterator end = list_.end();
- List::iterator it = insetIterator(pos);
- if (it != end it-pos == pos) {
- Inset * tmp = it-inset;
- it-inset = 0;
+ List::iterator it = list_.find(pos);
+ if (it != list_.end()) {
+ Inset * tmp = it-second;
+ it-second = 0;
return tmp;
}
return 0;
@@ -110,31 +84,32 @@
Inset * InsetList::get(pos_type pos) const
{
- List::const_iterator end = list_.end();
- List::const_iterator it = insetIterator(pos);
- if (it != end it-pos == pos)
- return it-inset;
+ List::const_iterator it = list_.find(pos);
+ if (it != list_.end())
+ return it-second;
return 0;
}
void InsetList::increasePosAfterPos(pos_type pos)
{
- List::iterator end = list_.end();
- List::iterator it = insetIterator(pos);
- for (; it != end; ++it) {
- ++it-pos;
- }
+ List oldlist = list_;
+ list_.clear();
+ List::iterator end = oldlist.end();
+ List::iterator it = oldlist.find(pos);
+ for (; it != end; ++it)
+ list_[it-first + 1] = it-second;
}
void InsetList::decreasePosAfterPos(pos_type pos)
{
- List::iterator end = list_.end();
- List::iterator it = insetIterator(pos);
- for (; it != end; ++it) {
- --it-pos;
- }
+ List oldlist = list_;
+ list_.clear();
+ List::iterator end = oldlist.end();
+ List::iterator it = oldlist.find(pos);
+ for (; it != end; ++it)
+ list_[it-first - 1] = it-second;
}
Index: InsetList.h
===
--- InsetList.h (revision 18766)
+++ InsetList.h (working copy)
@@ -14,7 +14,7 @@
#include support/types.h
-#include vector
+#include map
namespace lyx {
@@ -27,18 +27,8 @@
class InsetList {
public:
///
- class InsetTable {
- public:
- ///
- InsetTable(pos_type p, Inset * i) : pos(p), inset(i) {}
- ///
- pos_type pos;
- ///
- Inset * inset;
- };
+ typedef std::mappos_type,
Re: 20% speedup of paragraph redraw with simple patch
Seems to be false alarm. getInset does not show up very much anymore
without stdlib-debug. But there are still some interesting facts:
38% QPainter::drawText.
16% drawing of empty inline math insets (around every 20th character
in the text)
16% for metrics calculation
I think the only way to really reduce the amount to draw is to switch
to line based redrawing or even finer and relative coordinates for
scrolling.
Stefan
Alfredo Braunstein wrote:
Abdelrazak Younes wrote:
I am OK with it but maybe the real problem is why getInset is so
slow?
Looking at InsetList::insetIterator(pos_type pos), this is no wonder
really:
InsetList::iterator InsetList::insetIterator(pos_type pos)
{
InsetTable search_elem(pos, 0);
return lower_bound(list_.begin(), list_.end(), search_elem,
InsetTablePosLess());
}
InsetTable is basically 'pairpos, Inset*', so this InsetList is
basically reimplementing std::map in a less efficient way. Just
Are you sure it's less efficient?
No, that was just a guess.
AFAICS this is O(ln n) just like std::map,
constants may vary (in one side or the other).
replacing the 'vectorInsetTable' with a 'mappos, Inset*' will
clean
halves the code. And then you could just use the standard map
iterator
anywhere it makes sense; and I bet there is a lot of case were it
make
sense:
The code will be a bit cleaner maybe...
For sure ;-)
but it is self-contained and clean
enough, and has been working flawlessly for ages... so be sure
there is
really a gain if you are going to switch.
I am not proposing to switch before 1.5.0 but I might implement it
just for fun and ask Stefan to try it out with Shark ;-)
Abdel.
PGP.sig
Description: Signierter Teil der Nachricht
Re: 20% speedup of paragraph redraw with simple patch
Abdelrazak Younes wrote: Abdelrazak Younes wrote: Alfredo Braunstein wrote: but it is self-contained and clean enough, and has been working flawlessly for ages... so be sure there is really a gain if you are going to switch. I am not proposing to switch before 1.5.0 but I might implement it just for fun and ask Stefan to try it out with Shark ;-) Just for fun Stefan, could you try this out? Forget about it, it won't compile because of the multitude of -pos and -inset access. Abdel.
Re: 20% speedup of paragraph redraw with simple patch
Abdelrazak Younes wrote: Alfredo Braunstein wrote: but it is self-contained and clean enough, and has been working flawlessly for ages... so be sure there is really a gain if you are going to switch. I am not proposing to switch before 1.5.0 but I might implement it just for fun and ask Stefan to try it out with Shark ;-) Just for fun Stefan, could you try this out? You saw my patch to your first reply? I includes nearly the same patch. But without stdlib-debug there is no problem at all with all that. Stefan PGP.sig Description: Signierter Teil der Nachricht
Re: 20% speedup of paragraph redraw with simple patch
Abdelrazak == Abdelrazak Younes [EMAIL PROTECTED] writes: Abdelrazak Maybe not faster but a lot cleaner. Am I am pretty sure Abdelrazak that it will make the cases similar to the one found by Abdelrazak Stefan easier to optimize. Agreed. Second thought: what is the first term of the map? If it is the position, does this means that the map shall be recreated at each insertion? JMarc
Re: 20% speedup of paragraph redraw with simple patch
Stefan == Stefan Schimanski [EMAIL PROTECTED] writes: Stefan Seems to be false alarm. getInset does not show up very much Stefan anymore without stdlib-debug. But there are still some Stefan interesting facts: Stefan 38% QPainter::drawText. Looks more like what I would expect. Stefan 16% drawing of empty inline math insets (around every 20th Stefan character in the text) What do you mean? Stefan 16% for metrics calculation JMarc
Re: 20% speedup of paragraph redraw with simple patch
Stefan Schimanski wrote: Abdelrazak Younes wrote: Alfredo Braunstein wrote: but it is self-contained and clean enough, and has been working flawlessly for ages... so be sure there is really a gain if you are going to switch. I am not proposing to switch before 1.5.0 but I might implement it just for fun and ask Stefan to try it out with Shark ;-) Just for fun Stefan, could you try this out? You saw my patch to your first reply? I includes nearly the same patch. But without stdlib-debug there is no problem at all with all that. OK. Abdel.
Re: 20% speedup of paragraph redraw with simple patch
Stefan Schimanski wrote: Seems to be false alarm. getInset does not show up very much anymore without stdlib-debug. But there are still some interesting facts: 38% QPainter::drawText. This was expected on Mac. Still, IIRC the number is lower than what Bennett used to report a while ago. It shows that Qt4.3 is much better at drawing on Mac than previous version. Hopefully this number will keep decreasing with further release. 16% drawing of empty inline math insets (around every 20th character in the text) What is that? 16% for metrics calculation Calculation or hash table lookup? I think the only way to really reduce the amount to draw is to switch to line based redrawing or even finer and relative coordinates for scrolling. Once we re-organize the background painting in rowpainter (thus getting rid of wide() etc) I believe we will see a nice speedup because only the current line will have to be redrawn in all cases (within Inset or not). Abdel.
Re: 20% speedup of paragraph redraw with simple patch
Jean-Marc Lasgouttes wrote: Abdelrazak == Abdelrazak Younes [EMAIL PROTECTED] writes: Abdelrazak Maybe not faster but a lot cleaner. Am I am pretty sure Abdelrazak that it will make the cases similar to the one found by Abdelrazak Stefan easier to optimize. Agreed. Second thought: what is the first term of the map? In my first implementation the position. The atavantage is that then the Inset are ordered by position in memory and the code relies on that I think (but I am not sure). But the disavantage is: If it is the position, does this means that the map shall be recreated at each insertion? Right but I reckon this is not very costly, because we do something similar in the Paragraph list when inserting or deleting a paragraph. Abdel.
Re: 20% speedup of paragraph redraw with simple patch
Am 14.06.2007 um 18:44 schrieb Abdelrazak Younes: Stefan Schimanski wrote: Seems to be false alarm. getInset does not show up very much anymore without stdlib-debug. But there are still some interesting facts: 38% QPainter::drawText. This was expected on Mac. Still, IIRC the number is lower than what Bennett used to report a while ago. It shows that Qt4.3 is much better at drawing on Mac than previous version. Hopefully this number will keep decreasing with further release. 16% drawing of empty inline math insets (around every 20th character in the text) What is that? Basically the InsetMathHull::draw call with everything which follows. So at the end some QLPainter::line calls which turn out to be quite expensive IMO. 16% for metrics calculation Calculation or hash table lookup? The whole updateMetrics call, everything there summed up. I think the only way to really reduce the amount to draw is to switch to line based redrawing or even finer and relative coordinates for scrolling. Once we re-organize the background painting in rowpainter (thus getting rid of wide() etc) I believe we will see a nice speedup because only the current line will have to be redrawn in all cases (within Inset or not). That sounds good. Stefan PGP.sig Description: Signierter Teil der Nachricht
Re: 20% speedup of paragraph redraw with simple patch
On Thu, Jun 14, 2007 at 05:05:32PM +0200, Stefan Schimanski wrote:
I did some profiling of paragraph drawing. 20% of the whole time
while inserting characters and redrawing the screen was taken by
Paragraph::getInset calls, each for every character. This is stupid.
See the patch below for a loop iterating over the insets of a
paragraph instead. O(insetnumber) instead of O(charnumber * ln
insetnumber).
Stefan
Index: src/rowpainter.cpp
===
--- src/rowpainter.cpp(Revision 18765)
+++ src/rowpainter.cpp(Arbeitskopie)
@@ -958,10 +958,11 @@
// done here.
// JSpitzm: We should aim at removing wide() altogether
while retaining
// typing speed within insets.
- for (pos_type i = rit-pos() ; i != rit-endpos(); ++i) {
- Inset const * const in = par.getInset(i);
- if (in) {
- InsetText * t = const_castInsetText
*(in-asTextInset());
+ InsetList::const_iterator iit =
par.insetlist.insetIterator(rit-pos());
+ InsetList::const_iterator iend = par.insetlist.end();
+ for (; iit != iend iit-pos rit-endpos(); ++iit) {
+ if (iit-inset) {
+ InsetText * t = const_castInsetText
*(iit-inset-asTextInset());
if (t)
t-setWide(in_inset_alone_on_row
leftEdgeFixed
Good catch. Patch is fine with me.
[And I continue hating that wide() business ;-}]
Andre'
Re: 20% speedup of paragraph redraw with simple patch
Jean-Marc Lasgouttes wrote: Abdelrazak == Abdelrazak Younes [EMAIL PROTECTED] writes: Abdelrazak Maybe not faster but a lot cleaner. Am I am pretty sure Abdelrazak that it will make the cases similar to the one found by Abdelrazak Stefan easier to optimize. Agreed. Second thought: what is the first term of the map? If it is the position, does this means that the map shall be recreated at each insertion? JMarc Hmm, I just came across this yesterday when trying to figure out what was going on with bug 3011, and wondered about it. I'm not sure if this is what you mean or not, but it might be relevant... http://www.lyx.org/trac/browser/lyx-devel/trunk/src/Paragraph.cpp?rev=18599#L446
Re: 20% speedup of paragraph redraw with simple patch
On Thu, Jun 14, 2007 at 05:40:12PM +0200, Alfredo Braunstein wrote:
Abdelrazak Younes wrote:
I am OK with it but maybe the real problem is why getInset is so slow?
Looking at InsetList::insetIterator(pos_type pos), this is no wonder
really:
InsetList::iterator InsetList::insetIterator(pos_type pos)
{
InsetTable search_elem(pos, 0);
return lower_bound(list_.begin(), list_.end(), search_elem,
InsetTablePosLess());
}
InsetTable is basically 'pairpos, Inset*', so this InsetList is
basically reimplementing std::map in a less efficient way.
How do you [Abdel] arrive at the conclusion 'less efficient'?
Are you sure it's less efficient? AFAICS this is O(ln n) just like std::map,
constants may vary (in one side or the other).
A sorted vector filled should be cheaper than a map in any case.
replacing the 'vectorInsetTable' with a 'mappos, Inset*' will clean
halves the code. And then you could just use the standard map iterator
anywhere it makes sense; and I bet there is a lot of case were it make
sense:
The code will be a bit cleaner maybe... but it is self-contained and clean
enough, and has been working flawlessly for ages... so be sure there is
really a gain if you are going to switch.
Right.
Andre'
Re: 20% speedup of paragraph redraw with simple patch
On Thu, Jun 14, 2007 at 05:49:53PM +0200, Abdelrazak Younes wrote: Moreover, it remains to be seen whether the map is faster in the cases where the container typically has at most 10 elements. It might be that a stupid plain loop is faster... Maybe not faster but a lot cleaner. You may have noticed that users are complaining about speed, not on code cleanliness. Andre'
20% speedup of paragraph redraw with simple patch
I did some profiling of paragraph drawing. 20% of the whole time
while inserting characters and redrawing the screen was taken by
Paragraph::getInset calls, each for every character. This is stupid.
See the patch below for a loop iterating over the insets of a
paragraph instead. O(insetnumber) instead of O(charnumber * ln
insetnumber).
Stefan
Index: src/rowpainter.cpp
===
--- src/rowpainter.cpp (Revision 18765)
+++ src/rowpainter.cpp (Arbeitskopie)
@@ -958,10 +958,11 @@
// done here.
// JSpitzm: We should aim at removing wide() altogether while
retaining
// typing speed within insets.
- for (pos_type i = rit->pos() ; i != rit->endpos(); ++i) {
- Inset const * const in = par.getInset(i);
- if (in) {
- InsetText * t = const_cast(in->asTextInset());
+ InsetList::const_iterator iit = par.insetlist.insetIterator(rit-
>pos());
+ InsetList::const_iterator iend = par.insetlist.end();
+ for (; iit != iend && iit->pos < rit->endpos(); ++iit) {
+ if (iit->inset) {
+ InsetText * t = const_cast(iit->inset->asTextInset());
if (t)
t->setWide(in_inset_alone_on_row
&& leftEdgeFixed
parpaintinsetloop.patch
Description: Binary data
PGP.sig
Description: Signierter Teil der Nachricht
Re: 20% speedup of paragraph redraw with simple patch
> "Stefan" == Stefan Schimanski <[EMAIL PROTECTED]> writes: Stefan> I did some profiling of paragraph drawing. 20% of the whole Stefan> time while inserting characters and redrawing the screen was Stefan> taken by Paragraph::getInset calls, each for every character. Stefan> This is stupid. See the patch below for a loop iterating over Stefan> the insets of a paragraph instead. O(insetnumber) instead of Stefan> O(charnumber * ln insetnumber). Very good catch. Did you find it with Shark.app? Profiling with tools like gprof does not contain the cost of the actual painting and gives too much importance to loops like above. Note also that the argument insetIterator(pos) probably has a cost too, and that it is not needed IMO. Since one is iterating over the whole paragraph, can't we keep the same InsetList::iterator all the time? It is nice to see how a drawing optimization makes the drawing slower... JMarc
Re: 20% speedup of paragraph redraw with simple patch
Am 14.06.2007 um 17:19 schrieb Jean-Marc Lasgouttes: "Stefan" == Stefan Schimanski <[EMAIL PROTECTED]> writes: Stefan> I did some profiling of paragraph drawing. 20% of the whole Stefan> time while inserting characters and redrawing the screen was Stefan> taken by Paragraph::getInset calls, each for every character. Stefan> This is stupid. See the patch below for a loop iterating over Stefan> the insets of a paragraph instead. O(insetnumber) instead of Stefan> O(charnumber * ln insetnumber). Very good catch. Did you find it with Shark.app? Profiling with tools like gprof does not contain the cost of the actual painting and gives too much importance to loops like above. Yes, shark. And still on the way. I think there are still plenty of those things. Note also that the argument insetIterator(pos) probably has a cost too, and that it is not needed IMO. Since one is iterating over the whole paragraph, can't we keep the same InsetList::iterator all the time? Sure we can. But it does not show up in the profile currently. Note that it is only done once per line. It is nice to see how a drawing optimization makes the drawing slower... Didn't look what the loop is actually doing. Interesting if really have been meant like that. Stefan JMarc PGP.sig Description: Signierter Teil der Nachricht
Re: 20% speedup of paragraph redraw with simple patch
Stefan Schimanski wrote:
I did some profiling of paragraph drawing. 20% of the whole time while
inserting characters and redrawing the screen was taken by
Paragraph::getInset calls, each for every character.
The whole time? Including screen drawing?
This is stupid. See
the patch below for a loop iterating over the insets of a paragraph
instead. O(insetnumber) instead of O(charnumber * ln insetnumber).
I am OK with it but maybe the real problem is why getInset is so slow?
Looking at InsetList::insetIterator(pos_type pos), this is no wonder really:
InsetList::iterator InsetList::insetIterator(pos_type pos)
{
InsetTable search_elem(pos, 0);
return lower_bound(list_.begin(), list_.end(), search_elem,
InsetTablePosLess());
}
InsetTable is basically 'pair', so this InsetList is
basically reimplementing std::map in a less efficient way. Just
replacing the 'vector' with a 'map' will clean
halves the code. And then you could just use the standard map iterator
anywhere it makes sense; and I bet there is a lot of case were it make
sense:
Find all "getInset", Match case, Whole word, Subfolders, Find Results 1,
"lyx-trunk", "*.c;*.cpp;*.cxx;*.cc;*.tli;*.tlh;*.h;*.hpp;*.hxx;*.hh"
D:\devel\lyx\trunk\src\CutAndPaste.cpp(195):
!pars[pit].insetAllowed(tmpbuf->getInset(i)->lyxCode()))
D:\devel\lyx\trunk\src\DocIterator.cpp(72): return
paragraph().isInset(pos()) ? paragraph().getInset(pos()) : 0;
D:\devel\lyx\trunk\src\DocIterator.cpp(89): return
paragraph().isInset(pos() - 1) ? paragraph().getInset(pos() - 1) : 0;
D:\devel\lyx\trunk\src\DocIterator.cpp(106): return
paragraph().isInset(pos() - 1) ? paragraph().getInset(pos() - 1) : 0;
D:\devel\lyx\trunk\src\DocIterator.cpp(331):n =
paragraph().getInset(tip.pos());
D:\devel\lyx\trunk\src\DocIterator.cpp(520): n =
paragraph().getInset(tip.pos());
D:\devel\lyx\trunk\src\DocIterator.cpp(597):inset =
cs.paragraph().getInset(cs.pos());
D:\devel\lyx\trunk\src\output_plaintext.cpp(211): int len =
par.getInset(i)->plaintext(buf, os, rp);
D:\devel\lyx\trunk\src\Paragraph.cpp(317):
owner_->getInset(pos)->setChange(change);
D:\devel\lyx\trunk\src\Paragraph.cpp(334):
owner_->getInset(pos)->setChange(change);
D:\devel\lyx\trunk\src\Paragraph.cpp(357):
owner_->getInset(pos)->acceptChanges(bparams);
D:\devel\lyx\trunk\src\Paragraph.cpp(366):
owner_->getInset(pos)->acceptChanges(bparams);
D:\devel\lyx\trunk\src\Paragraph.cpp(395):
owner_->getInset(pos)->rejectChanges(bparams);
D:\devel\lyx\trunk\src\Paragraph.cpp(681):
owner_->getInset(i)->plaintext(buf, os, runparams);
D:\devel\lyx\trunk\src\Paragraph.cpp(690): Inset * inset =
owner_->getInset(i);
D:\devel\lyx\trunk\src\Paragraph.cpp(1143): Inset const * inset =
getInset(i);
D:\devel\lyx\trunk\src\Paragraph.cpp(2180): Inset const * inset =
getInset(i);
D:\devel\lyx\trunk\src\Paragraph.cpp(2205): Inset const * inset =
getInset(i);
D:\devel\lyx\trunk\src\Paragraph.cpp(2223): Inset const * inset =
getInset(i);
D:\devel\lyx\trunk\src\Paragraph.cpp(2284): Inset const * inset =
getInset(i);
D:\devel\lyx\trunk\src\Paragraph.cpp(2311): &&
getInset(pos)->lyxCode() == Inset::NEWLINE_CODE;
D:\devel\lyx\trunk\src\Paragraph.cpp(2319): || (c ==
Paragraph::META_INSET && getInset(pos) &&
D:\devel\lyx\trunk\src\Paragraph.cpp(2320):
getInset(pos)->isLineSeparator());
D:\devel\lyx\trunk\src\Paragraph.cpp(2328): return
getInset(pos)->isLetter();
D:\devel\lyx\trunk\src\Paragraph.cpp(2408):
getInset(i)->textString(buffer, os);
D:\devel\lyx\trunk\src\Paragraph.h(71): /// try getInset() and
crash. We should fix
D:\devel\lyx\trunk\src\Paragraph.h(314): Inset * getInset(pos_type pos) {
D:\devel\lyx\trunk\src\Paragraph.h(318): Inset const *
getInset(pos_type pos) const {
D:\devel\lyx\trunk\src\Paragraph.h(325): &&
getInset(pos)->lyxCode() == Inset::HFILL_CODE;
D:\devel\lyx\trunk\src\paragraph_funcs.cpp(40): if
(fromPar.getInset(fromPos)) {
D:\devel\lyx\trunk\src\rowpainter.cpp(182): Inset const * inset =
par_.getInset(pos);
D:\devel\lyx\trunk\src\rowpainter.cpp(422):
par_.getInset(pos)->descent());
D:\devel\lyx\trunk\src\rowpainter.cpp(787): &&
isHighlyEditableInset(par_.getInset(pos));
D:\devel\lyx\trunk\src\rowpainter.cpp(962): Inset const * const in
= par.getInset(i);
D:\devel\lyx\trunk\src\Text.cpp(385): return
par.getInset(pos)->width();
D:\devel\lyx\trunk\src\Text.cpp(566): &&
par.getInset(pos)->display())
D:\devel\lyx\trunk\src\Text2.cpp(315):
pars_[pit].getInset(pos)->noFontChange());
D:\devel\lyx\trunk\src\Text2.cpp(317): Inset * const inset =
pars_[pit].getInset(pos);
D:\devel\lyx\trunk\src\Text2.cpp(516):
pars_[pit].getInset(pos)->noFontChange())
D:\devel\lyx\trunk\src\Text2.cpp(927): Inset * insetBefore = pos?
pars_[pit].getInset(pos - 1): 0;
Re: 20% speedup of paragraph redraw with simple patch
Am 14.06.2007 um 17:27 schrieb Abdelrazak Younes:
Stefan Schimanski wrote:
I did some profiling of paragraph drawing. 20% of the whole time
while inserting characters and redrawing the screen was taken by
Paragraph::getInset calls, each for every character.
The whole time? Including screen drawing?
Yes, including everything. But using stdlib-debug I have to admit.
Compiling now without. I guess it is less problematic then.
This is stupid. See the patch below for a loop iterating over the
insets of a paragraph instead. O(insetnumber) instead of O
(charnumber * ln insetnumber).
I am OK with it but maybe the real problem is why getInset is so
slow? Looking at InsetList::insetIterator(pos_type pos), this is no
wonder really:
InsetList::iterator InsetList::insetIterator(pos_type pos)
{
InsetTable search_elem(pos, 0);
return lower_bound(list_.begin(), list_.end(), search_elem,
InsetTablePosLess());
}
InsetTable is basically 'pair', so this InsetList is
basically reimplementing std::map in a less efficient way. Just
replacing the 'vector' with a 'map' will
clean halves the code. And then you could just use the standard map
iterator anywhere it makes sense; and I bet there is a lot of case
were it make sense:
mapinsetlist.patch
Description: Binary data
Stefan
PGP.sig
Description: Signierter Teil der Nachricht
Re: 20% speedup of paragraph redraw with simple patch
Stefan Schimanski wrote: Am 14.06.2007 um 17:27 schrieb Abdelrazak Younes: Stefan Schimanski wrote: I did some profiling of paragraph drawing. 20% of the whole time while inserting characters and redrawing the screen was taken by Paragraph::getInset calls, each for every character. The whole time? Including screen drawing? Yes, including everything. But using stdlib-debug I have to admit. Compiling now without. I guess it is less problematic then. I am pretty sure it won't be that problematic then... too bad! ;-) Abdel.
Re: 20% speedup of paragraph redraw with simple patch
Abdelrazak Younes wrote:
> I am OK with it but maybe the real problem is why getInset is so slow?
> Looking at InsetList::insetIterator(pos_type pos), this is no wonder
> really:
>
> InsetList::iterator InsetList::insetIterator(pos_type pos)
> {
> InsetTable search_elem(pos, 0);
> return lower_bound(list_.begin(), list_.end(), search_elem,
> InsetTablePosLess());
> }
>
> InsetTable is basically 'pair', so this InsetList is
> basically reimplementing std::map in a less efficient way. Just
Are you sure it's less efficient? AFAICS this is O(ln n) just like std::map,
constants may vary (in one side or the other).
> replacing the 'vector' with a 'map' will clean
> halves the code. And then you could just use the standard map iterator
> anywhere it makes sense; and I bet there is a lot of case were it make
> sense:
The code will be a bit cleaner maybe... but it is self-contained and clean
enough, and has been working flawlessly for ages... so be sure there is
really a gain if you are going to switch.
A/
Re: 20% speedup of paragraph redraw with simple patch
> "Stefan" == Stefan Schimanski <[EMAIL PROTECTED]> writes: Stefan> Yes, including everything. But using stdlib-debug I have to Stefan> admit. Compiling now without. I guess it is less problematic Stefan> then. Or maybe not problematic at all. stdlib is really very costly in terms of iterating over stl constructs. Profiling with it is kind of useless... >> InsetTable is basically 'pair', so this InsetList is basically >> reimplementing std::map in a less efficient way. Just replacing the >> 'vector' with a 'map' will clean halves the code. And >> then you could just use the standard map iterator anywhere it makes >> sense; and I bet there is a lot of case were it make sense: But this is not for now, right? Moreover, it remains to be seen whether the map is faster in the cases where the container typically has at most 10 elements. It might be that a stupid plain loop is faster... JMarc
Re: 20% speedup of paragraph redraw with simple patch
Jean-Marc Lasgouttes wrote: "Stefan" == Stefan Schimanski <[EMAIL PROTECTED]> writes: Stefan> Yes, including everything. But using stdlib-debug I have to Stefan> admit. Compiling now without. I guess it is less problematic Stefan> then. Or maybe not problematic at all. stdlib is really very costly in terms of iterating over stl constructs. Profiling with it is kind of useless... InsetTable is basically 'pair', so this InsetList is basically reimplementing std::map in a less efficient way. Just replacing the 'vector' with a 'map' will clean halves the code. And then you could just use the standard map iterator anywhere it makes sense; and I bet there is a lot of case were it make sense: But this is not for now, right? Right. Moreover, it remains to be seen whether the map is faster in the cases where the container typically has at most 10 elements. It might be that a stupid plain loop is faster... Maybe not faster but a lot cleaner. Am I am pretty sure that it will make the cases similar to the one found by Stefan easier to optimize. Abdel.
Re: 20% speedup of paragraph redraw with simple patch
Alfredo Braunstein wrote:
Abdelrazak Younes wrote:
I am OK with it but maybe the real problem is why getInset is so slow?
Looking at InsetList::insetIterator(pos_type pos), this is no wonder
really:
InsetList::iterator InsetList::insetIterator(pos_type pos)
{
InsetTable search_elem(pos, 0);
return lower_bound(list_.begin(), list_.end(), search_elem,
InsetTablePosLess());
}
InsetTable is basically 'pair', so this InsetList is
basically reimplementing std::map in a less efficient way. Just
Are you sure it's less efficient?
No, that was just a guess.
AFAICS this is O(ln n) just like std::map,
constants may vary (in one side or the other).
replacing the 'vector' with a 'map' will clean
halves the code. And then you could just use the standard map iterator
anywhere it makes sense; and I bet there is a lot of case were it make
sense:
The code will be a bit cleaner maybe...
For sure ;-)
but it is self-contained and clean
enough, and has been working flawlessly for ages... so be sure there is
really a gain if you are going to switch.
I am not proposing to switch before 1.5.0 but I might implement it just
for fun and ask Stefan to try it out with Shark ;-)
Abdel.
Re: 20% speedup of paragraph redraw with simple patch
Abdelrazak Younes wrote:
Alfredo Braunstein wrote:
but it is self-contained and clean
enough, and has been working flawlessly for ages... so be sure there is
really a gain if you are going to switch.
I am not proposing to switch before 1.5.0 but I might implement it just
for fun and ask Stefan to try it out with Shark ;-)
Just for fun Stefan, could you try this out?
Abdel.
Index: InsetList.cpp
===
--- InsetList.cpp (revision 18766)
+++ InsetList.cpp (working copy)
@@ -24,25 +24,7 @@
namespace lyx {
using std::endl;
-using std::lower_bound;
-
-namespace {
-
-typedef InsetList::InsetTable Table;
-
-class InsetTablePosLess : public std::binary_function {
-public:
- bool operator()(Table const & t1, Table const & t2) const
- {
- return t1.pos < t2.pos;
- }
-};
-
-} // namespace anon
-
-
-
InsetList::~InsetList()
{
// If we begin storing a shared_ptr in the List
@@ -50,46 +32,39 @@
List::iterator it = list_.begin();
List::iterator end = list_.end();
for (; it != end; ++it) {
- delete it->inset;
+ delete it->second;
}
}
InsetList::iterator InsetList::insetIterator(pos_type pos)
{
- InsetTable search_elem(pos, 0);
- return lower_bound(list_.begin(), list_.end(), search_elem,
- InsetTablePosLess());
+ return list_.find(pos);
}
InsetList::const_iterator InsetList::insetIterator(pos_type pos) const
{
- InsetTable search_elem(pos, 0);
- return lower_bound(list_.begin(), list_.end(), search_elem,
- InsetTablePosLess());
+ return list_.find(pos);
}
void InsetList::insert(Inset * inset, pos_type pos)
{
- List::iterator end = list_.end();
- List::iterator it = insetIterator(pos);
- if (it != end && it->pos == pos) {
+ List::iterator it = list_.find(pos);
+ if (it != list_.end())
lyxerr << "ERROR (InsetList::insert): "
<< "There is an inset in position: " << pos << endl;
- } else {
- list_.insert(it, InsetTable(pos, inset));
- }
+ else
+ list_[pos] = inset;;
}
void InsetList::erase(pos_type pos)
{
- List::iterator end = list_.end();
- List::iterator it = insetIterator(pos);
- if (it != end && it->pos == pos) {
- delete it->inset;
+ List::iterator it = list_.find(pos);
+ if (it != list_.end()) {
+ delete it->second;
list_.erase(it);
}
}
@@ -97,11 +72,10 @@
Inset * InsetList::release(pos_type pos)
{
- List::iterator end = list_.end();
- List::iterator it = insetIterator(pos);
- if (it != end && it->pos == pos) {
- Inset * tmp = it->inset;
- it->inset = 0;
+ List::iterator it = list_.find(pos);
+ if (it != list_.end()) {
+ Inset * tmp = it->second;
+ it->second = 0;
return tmp;
}
return 0;
@@ -110,31 +84,32 @@
Inset * InsetList::get(pos_type pos) const
{
- List::const_iterator end = list_.end();
- List::const_iterator it = insetIterator(pos);
- if (it != end && it->pos == pos)
- return it->inset;
+ List::const_iterator it = list_.find(pos);
+ if (it != list_.end())
+ return it->second;
return 0;
}
void InsetList::increasePosAfterPos(pos_type pos)
{
- List::iterator end = list_.end();
- List::iterator it = insetIterator(pos);
- for (; it != end; ++it) {
- ++it->pos;
- }
+ List oldlist = list_;
+ list_.clear();
+ List::iterator end = oldlist.end();
+ List::iterator it = oldlist.find(pos);
+ for (; it != end; ++it)
+ list_[it->first + 1] = it->second;
}
void InsetList::decreasePosAfterPos(pos_type pos)
{
- List::iterator end = list_.end();
- List::iterator it = insetIterator(pos);
- for (; it != end; ++it) {
- --it->pos;
- }
+ List oldlist = list_;
+ list_.clear();
+ List::iterator end = oldlist.end();
+ List::iterator it = oldlist.find(pos);
+ for (; it != end; ++it)
+ list_[it->first - 1] = it->second;
}
Index: InsetList.h
===
--- InsetList.h (revision 18766)
+++ InsetList.h (working copy)
@@ -14,7 +14,7 @@
#include "support/types.h"
-#include
+#include
namespace lyx {
@@ -27,18 +27,8 @@
class InsetList {
public:
///
- class InsetTable {
- public:
- ///
- InsetTable(pos_type p, Inset * i) : pos(p), inset(i) {}
- ///
- pos_type pos;
- ///
- Inset * inset;
-
Re: 20% speedup of paragraph redraw with simple patch
Seems to be false alarm. getInset does not show up very much anymore
without stdlib-debug. But there are still some interesting facts:
38% QPainter::drawText.
16% drawing of empty inline math insets (around every 20th character
in the text)
16% for metrics calculation
I think the only way to really reduce the amount to draw is to switch
to line based redrawing or even finer and relative coordinates for
scrolling.
Stefan
Alfredo Braunstein wrote:
Abdelrazak Younes wrote:
I am OK with it but maybe the real problem is why getInset is so
slow?
Looking at InsetList::insetIterator(pos_type pos), this is no wonder
really:
InsetList::iterator InsetList::insetIterator(pos_type pos)
{
InsetTable search_elem(pos, 0);
return lower_bound(list_.begin(), list_.end(), search_elem,
InsetTablePosLess());
}
InsetTable is basically 'pair', so this InsetList is
basically reimplementing std::map in a less efficient way. Just
Are you sure it's less efficient?
No, that was just a guess.
AFAICS this is O(ln n) just like std::map,
constants may vary (in one side or the other).
replacing the 'vector' with a 'map' will
clean
halves the code. And then you could just use the standard map
iterator
anywhere it makes sense; and I bet there is a lot of case were it
make
sense:
The code will be a bit cleaner maybe...
For sure ;-)
but it is self-contained and clean
enough, and has been working flawlessly for ages... so be sure
there is
really a gain if you are going to switch.
I am not proposing to switch before 1.5.0 but I might implement it
just for fun and ask Stefan to try it out with Shark ;-)
Abdel.
PGP.sig
Description: Signierter Teil der Nachricht
Re: 20% speedup of paragraph redraw with simple patch
Abdelrazak Younes wrote: Abdelrazak Younes wrote: Alfredo Braunstein wrote: but it is self-contained and clean enough, and has been working flawlessly for ages... so be sure there is really a gain if you are going to switch. I am not proposing to switch before 1.5.0 but I might implement it just for fun and ask Stefan to try it out with Shark ;-) Just for fun Stefan, could you try this out? Forget about it, it won't compile because of the multitude of ->pos and ->inset access. Abdel.
Re: 20% speedup of paragraph redraw with simple patch
Abdelrazak Younes wrote: Alfredo Braunstein wrote: but it is self-contained and clean enough, and has been working flawlessly for ages... so be sure there is really a gain if you are going to switch. I am not proposing to switch before 1.5.0 but I might implement it just for fun and ask Stefan to try it out with Shark ;-) Just for fun Stefan, could you try this out? You saw my patch to your first reply? I includes nearly the same patch. But without stdlib-debug there is no problem at all with all that. Stefan PGP.sig Description: Signierter Teil der Nachricht
Re: 20% speedup of paragraph redraw with simple patch
> "Abdelrazak" == Abdelrazak Younes <[EMAIL PROTECTED]> writes: Abdelrazak> Maybe not faster but a lot cleaner. Am I am pretty sure Abdelrazak> that it will make the cases similar to the one found by Abdelrazak> Stefan easier to optimize. Agreed. Second thought: what is the first term of the map? If it is the position, does this means that the map shall be recreated at each insertion? JMarc
Re: 20% speedup of paragraph redraw with simple patch
> "Stefan" == Stefan Schimanski <[EMAIL PROTECTED]> writes: Stefan> Seems to be false alarm. getInset does not show up very much Stefan> anymore without stdlib-debug. But there are still some Stefan> interesting facts: Stefan> 38% QPainter::drawText. Looks more like what I would expect. Stefan> 16% drawing of empty inline math insets (around every 20th Stefan> character in the text) What do you mean? Stefan> 16% for metrics calculation JMarc
Re: 20% speedup of paragraph redraw with simple patch
Stefan Schimanski wrote: Abdelrazak Younes wrote: Alfredo Braunstein wrote: but it is self-contained and clean enough, and has been working flawlessly for ages... so be sure there is really a gain if you are going to switch. I am not proposing to switch before 1.5.0 but I might implement it just for fun and ask Stefan to try it out with Shark ;-) Just for fun Stefan, could you try this out? You saw my patch to your first reply? I includes nearly the same patch. But without stdlib-debug there is no problem at all with all that. OK. Abdel.
Re: 20% speedup of paragraph redraw with simple patch
Stefan Schimanski wrote: Seems to be false alarm. getInset does not show up very much anymore without stdlib-debug. But there are still some interesting facts: 38% QPainter::drawText. This was expected on Mac. Still, IIRC the number is lower than what Bennett used to report a while ago. It shows that Qt4.3 is much better at drawing on Mac than previous version. Hopefully this number will keep decreasing with further release. 16% drawing of empty inline math insets (around every 20th character in the text) What is that? 16% for metrics calculation Calculation or hash table lookup? I think the only way to really reduce the amount to draw is to switch to line based redrawing or even finer and relative coordinates for scrolling. Once we re-organize the background painting in rowpainter (thus getting rid of wide() etc) I believe we will see a nice speedup because only the current line will have to be redrawn in all cases (within Inset or not). Abdel.
Re: 20% speedup of paragraph redraw with simple patch
Jean-Marc Lasgouttes wrote: "Abdelrazak" == Abdelrazak Younes <[EMAIL PROTECTED]> writes: Abdelrazak> Maybe not faster but a lot cleaner. Am I am pretty sure Abdelrazak> that it will make the cases similar to the one found by Abdelrazak> Stefan easier to optimize. Agreed. Second thought: what is the first term of the map? In my first implementation the position. The atavantage is that then the Inset are ordered by position in memory and the code relies on that I think (but I am not sure). But the disavantage is: If it is the position, does this means that the map shall be recreated at each insertion? Right but I reckon this is not very costly, because we do something similar in the Paragraph list when inserting or deleting a paragraph. Abdel.
Re: 20% speedup of paragraph redraw with simple patch
Am 14.06.2007 um 18:44 schrieb Abdelrazak Younes: Stefan Schimanski wrote: Seems to be false alarm. getInset does not show up very much anymore without stdlib-debug. But there are still some interesting facts: 38% QPainter::drawText. This was expected on Mac. Still, IIRC the number is lower than what Bennett used to report a while ago. It shows that Qt4.3 is much better at drawing on Mac than previous version. Hopefully this number will keep decreasing with further release. 16% drawing of empty inline math insets (around every 20th character in the text) What is that? Basically the InsetMathHull::draw call with everything which follows. So at the end some QLPainter::line calls which turn out to be quite expensive IMO. 16% for metrics calculation Calculation or hash table lookup? The whole updateMetrics call, everything there summed up. I think the only way to really reduce the amount to draw is to switch to line based redrawing or even finer and relative coordinates for scrolling. Once we re-organize the background painting in rowpainter (thus getting rid of wide() etc) I believe we will see a nice speedup because only the current line will have to be redrawn in all cases (within Inset or not). That sounds good. Stefan PGP.sig Description: Signierter Teil der Nachricht
Re: 20% speedup of paragraph redraw with simple patch
On Thu, Jun 14, 2007 at 05:05:32PM +0200, Stefan Schimanski wrote:
> I did some profiling of paragraph drawing. 20% of the whole time
> while inserting characters and redrawing the screen was taken by
> Paragraph::getInset calls, each for every character. This is stupid.
> See the patch below for a loop iterating over the insets of a
> paragraph instead. O(insetnumber) instead of O(charnumber * ln
> insetnumber).
>
> Stefan
>
> Index: src/rowpainter.cpp
> ===
> --- src/rowpainter.cpp(Revision 18765)
> +++ src/rowpainter.cpp(Arbeitskopie)
> @@ -958,10 +958,11 @@
> // done here.
> // JSpitzm: We should aim at removing wide() altogether
> while retaining
> // typing speed within insets.
> - for (pos_type i = rit->pos() ; i != rit->endpos(); ++i) {
> - Inset const * const in = par.getInset(i);
> - if (in) {
> - InsetText * t = const_cast *>(in->asTextInset());
> + InsetList::const_iterator iit =
> par.insetlist.insetIterator(rit->pos());
> + InsetList::const_iterator iend = par.insetlist.end();
> + for (; iit != iend && iit->pos < rit->endpos(); ++iit) {
> + if (iit->inset) {
> + InsetText * t = const_cast *>(iit->inset->asTextInset());
> if (t)
> t->setWide(in_inset_alone_on_row
> && leftEdgeFixed
Good catch. Patch is fine with me.
[And I continue hating that wide() business ;-}]
Andre'
Re: 20% speedup of paragraph redraw with simple patch
Jean-Marc Lasgouttes wrote: "Abdelrazak" == Abdelrazak Younes <[EMAIL PROTECTED]> writes: Abdelrazak> Maybe not faster but a lot cleaner. Am I am pretty sure Abdelrazak> that it will make the cases similar to the one found by Abdelrazak> Stefan easier to optimize. Agreed. Second thought: what is the first term of the map? If it is the position, does this means that the map shall be recreated at each insertion? JMarc Hmm, I just came across this yesterday when trying to figure out what was going on with bug 3011, and wondered about it. I'm not sure if this is what you mean or not, but it might be relevant... http://www.lyx.org/trac/browser/lyx-devel/trunk/src/Paragraph.cpp?rev=18599#L446
Re: 20% speedup of paragraph redraw with simple patch
On Thu, Jun 14, 2007 at 05:40:12PM +0200, Alfredo Braunstein wrote:
> Abdelrazak Younes wrote:
>
> > I am OK with it but maybe the real problem is why getInset is so slow?
> > Looking at InsetList::insetIterator(pos_type pos), this is no wonder
> > really:
> >
> > InsetList::iterator InsetList::insetIterator(pos_type pos)
> > {
> > InsetTable search_elem(pos, 0);
> > return lower_bound(list_.begin(), list_.end(), search_elem,
> > InsetTablePosLess());
> > }
> >
> > InsetTable is basically 'pair', so this InsetList is
> > basically reimplementing std::map in a less efficient way.
How do you [Abdel] arrive at the conclusion 'less efficient'?
> Are you sure it's less efficient? AFAICS this is O(ln n) just like std::map,
> constants may vary (in one side or the other).
A sorted vector filled should be cheaper than a map in any case.
> > replacing the 'vector' with a 'map' will clean
> > halves the code. And then you could just use the standard map iterator
> > anywhere it makes sense; and I bet there is a lot of case were it make
> > sense:
>
> The code will be a bit cleaner maybe... but it is self-contained and clean
> enough, and has been working flawlessly for ages... so be sure there is
> really a gain if you are going to switch.
Right.
Andre'
Re: 20% speedup of paragraph redraw with simple patch
On Thu, Jun 14, 2007 at 05:49:53PM +0200, Abdelrazak Younes wrote: > >Moreover, it remains to be seen whether the map is faster in the cases > >where the container typically has at most 10 elements. It might be > >that a stupid plain loop is faster... > > Maybe not faster but a lot cleaner. You may have noticed that users are complaining about speed, not on code cleanliness. Andre'
