Re: [patch] store offset instead of ParagraphList::iterator in Cursor
Andre Poenitz [EMAIL PROTECTED] writes: | This is a patch to use 'par_type' offsets to ownerParagraphs().begin() | in LyXCursor. | The drawback is obvious: we have O(n) access in some cases where we had | O(1) before. Only some cases? | However,I have not seen _any_ indication that this is | noticable after playing around with the UserGuide. | In any case, the benefits seem to clearly outweigh this: LyXCursor is | now 'copiable' and we can add asserts to the 'getPar()' set of functions | to catch accesses to 'uninitialized' cursor data early. And we've lost a | few dependency on ParagraphList_fwd.h. I have no idea what 'copiable' is. The cursor is perfectly copiable with the iterator so what does this really change? -- Lgb
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
Andre Poenitz wrote: And we've lost a few dependency on ParagraphList_fwd.h. which is a non-issue in my book since it drags in system files only. Ok, ok, so you don't like list. I note that support/types.h still drags in vector. -- Angus
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
Angus Leeming [EMAIL PROTECTED] writes: | Andre Poenitz wrote: And we've lost a few dependency on ParagraphList_fwd.h. | which is a non-issue in my book since it drags in system files only. | Ok, ok, so you don't like list. I note that support/types.h still | drags in vector. And I claim that you can drag in a bunch of headers without noticing any effect. Time to stop this header phobia. -- Lgb
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
Lars Gullik Bjønnes wrote:
| Andre Poenitz wrote:
And we've lost a few dependency on ParagraphList_fwd.h.
| which is a non-issue in my book since it drags in system files
| only. Ok, ok, so you don't like list. I note that
| support/types.h still drags in vector.
And I claim that you can drag in a bunch of headers without noticing
any effect.
Time to stop this header phobia.
I agree, but only for system headers. Unnecessary project headers lead
to the re-compilation of unnecessarily large chunks of the tree each
time they are changed.
Anyway, let's see if we can back that up:
$ cat lars.C
#include map
#include vector
#include string
#include list
int main() {
return 0;
}
$ time g++ -o lars lars.C
real0m0.684s
user0m0.420s
sys 0m0.030s
]$ cat andre.C
int main() {
return 0;
}
$ time g++ -o andre andre.C
real0m0.152s
user0m0.150s
sys 0m0.000s
Conclusion: dragging in those headers costs half a second.
$ cd lyx/devel/src find . -name '*.C' | wc -l
818
Conclusion: the worst case is that this costs us 400secs on a full
compile.
--
Angus
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
On Thu, Oct 09, 2003 at 10:18:58AM +0200, Lars Gullik Bjønnes wrote: Andre Poenitz [EMAIL PROTECTED] writes: | This is a patch to use 'par_type' offsets to ownerParagraphs().begin() | in LyXCursor. | The drawback is obvious: we have O(n) access in some cases where we had | O(1) before. Only some cases? Nitpicking mode? No, not all accesses are O(n), and if the chage is propagated further it is to be expected that some of the current translations offset - iterator will be removed again. | However,I have not seen _any_ indication that this is | noticable after playing around with the UserGuide. | In any case, the benefits seem to clearly outweigh this: LyXCursor is | now 'copiable' and we can add asserts to the 'getPar()' set of functions | to catch accesses to 'uninitialized' cursor data early. And we've lost a | few dependency on ParagraphList_fwd.h. I have no idea what 'copiable' is. The cursor is perfectly copiable But not structures based on it. with the iterator so what does this really change? InsetText is currently pretty fragile, most notably, copying does not work as e.g. the tabular code assumes. Debugging suggests that we have a problem with cursors accessing not existing paragraphs. Looking at the code this might well be possible: If the paragraph list is changed heavily (say assigned to) we invalidate all iterators to it, most notably those hidden in the Cursors belonging to the InsetText's LyXText. For smaller changes (say erasing of one element), we invalidate only a few 'unlucky' iterators. Some times it happens to work. There are several places in the code where this is not taken care of (most places actually), and frankly, I do neither want to figure out where all of these places are nor do I want to add glue code 'just to make it work' as long as there 'automatic' solutions. One 'automatic' solution (and the simplest I can think of) is to use offsets instead of iterators. These are stable, can be copied around at will and checked for validity for each access if necessary. There is neither glue code needed, and there is no need to hunt down and check all occurences in the 'user code'. Andre' -- Those who desire to give up Freedom in order to gain Security, will not have, nor do they deserve, either one. (T. Jefferson or B. Franklin or both...)
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
On Thu, Oct 09, 2003 at 09:31:13AM +, Angus Leeming wrote: Andre Poenitz wrote: And we've lost a few dependency on ParagraphList_fwd.h. which is a non-issue in my book since it drags in system files only. Ok, ok, so you don't like list. I note that support/types.h still drags in vector. Those lost dependencies are not the reason for the patch, they are just a bonus. Andre' -- Those who desire to give up Freedom in order to gain Security, will not have, nor do they deserve, either one. (T. Jefferson or B. Franklin or both...)
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
On Thu, Oct 09, 2003 at 10:46:56AM +0200, Lars Gullik Bjønnes wrote: Angus Leeming [EMAIL PROTECTED] writes: | Andre Poenitz wrote: And we've lost a few dependency on ParagraphList_fwd.h. | which is a non-issue in my book since it drags in system files only. | Ok, ok, so you don't like list. I note that support/types.h still | drags in vector. And I claim that you can drag in a bunch of headers without noticing any effect. Time to stop this header phobia. H***, this is _no_ 'I don't like list' patch. This is preliminary work to fix these 'cri' bugs on bugzilla. I really don't know how one can make patches palatable to you. If it is small, it is not doing 'enough'. If it is big, it's doing too much. And there's, of course, that bit in between which is doing not enough while doing too much... Than there are speedup changes, which are not nice, and speed is not important anyway. There are changes _theoretically_ losing speed, which are not nice as we might lose performance, and performance is important. *sigh* Andre'
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
On Thu, Oct 09, 2003 at 09:55:32AM +, Angus Leeming wrote: Conclusion: the worst case is that this costs us 400secs on a full compile. Nice numbers, but you miss the point. I am currently trying to fix crashs, not #includes.. Andre' -- Those who desire to give up Freedom in order to gain Security, will not have, nor do they deserve, either one. (T. Jefferson or B. Franklin or both...)
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
Andre Poenitz [EMAIL PROTECTED] writes: | On Thu, Oct 09, 2003 at 10:18:58AM +0200, Lars Gullik Bjønnes wrote: Andre Poenitz [EMAIL PROTECTED] writes: | This is a patch to use 'par_type' offsets to ownerParagraphs().begin() | in LyXCursor. | The drawback is obvious: we have O(n) access in some cases where we had | O(1) before. Only some cases? | Nitpicking mode? Lack of information/description mode. | No, not all accesses are O(n), and if the chage is propagated further it | is to be expected that some of the current translations offset - | iterator will be removed again. | However,I have not seen _any_ indication that this is | noticable after playing around with the UserGuide. | In any case, the benefits seem to clearly outweigh this: LyXCursor is | now 'copiable' and we can add asserts to the 'getPar()' set of functions | to catch accesses to 'uninitialized' cursor data early. And we've lost a | few dependency on ParagraphList_fwd.h. I have no idea what 'copiable' is. The cursor is perfectly copiable | But not structures based on it. with the iterator so what does this really change? | InsetText is currently pretty fragile, most notably, copying does not | work as e.g. the tabular code assumes. | Debugging suggests that we have a problem with cursors accessing not | existing paragraphs. Looking at the code this might well be possible: If | the paragraph list is changed heavily (say assigned to) we invalidate | all iterators to it, most notably those hidden in the Cursors belonging | to the InsetText's LyXText. For smaller changes (say erasing of one | element), we invalidate only a few 'unlucky' iterators. Some times it | happens to work. But won't this be the case with offsets as well? Only get silent failure instead of crash, but the offset is still invalid. (In that it points somewhere else than intended.) | There are several places in the code where this is not taken care of | (most places actually), and frankly, I do neither want to figure out | where all of these places are nor do I want to add glue code 'just to | make it work' as long as there 'automatic' solutions. | One 'automatic' solution (and the simplest I can think of) is to use | offsets instead of iterators. These are stable, can be copied around | at will and checked for validity for each access if necessary. There is | neither glue code needed, and there is no need to hunt down and check | all occurences in the 'user code'. You cannot really check an offset for validity (except in a very few special cases). An offset is almost always valid even if it points to the wrong place. -- Lgb
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
Andre Poenitz [EMAIL PROTECTED] writes: | On Thu, Oct 09, 2003 at 09:31:13AM +, Angus Leeming wrote: Andre Poenitz wrote: And we've lost a few dependency on ParagraphList_fwd.h. which is a non-issue in my book since it drags in system files only. Ok, ok, so you don't like list. I note that support/types.h still drags in vector. | Those lost dependencies are not the reason for the patch, they are just | a bonus. What type does std::distance return? We should use that for the offsets. -- Lgb
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
Andre Poenitz [EMAIL PROTECTED] writes: | On Thu, Oct 09, 2003 at 10:46:56AM +0200, Lars Gullik Bjønnes wrote: Angus Leeming [EMAIL PROTECTED] writes: | Andre Poenitz wrote: And we've lost a few dependency on ParagraphList_fwd.h. | which is a non-issue in my book since it drags in system files only. | Ok, ok, so you don't like list. I note that support/types.h still | drags in vector. And I claim that you can drag in a bunch of headers without noticing any effect. Time to stop this header phobia. | H***, this is _no_ 'I don't like list' patch. Removing unneeded headers - fine. Claiming that this is a bonus - not. | This is preliminary work to fix these 'cri' bugs on bugzilla. | I really don't know how one can make patches palatable to you. | If it is small, it is not doing 'enough'. If it is big, it's doing too | much. And there's, of course, that bit in between which is doing not | enough while doing too much... | Than there are speedup changes, which are not nice, and speed is not | important anyway. There are changes _theoretically_ losing speed, which | are not nice as we might lose performance, and performance is | important. | *sigh* You are no way ahead of me. I am trying to fathom what this iterator - offset change will really result in. Are there hidden dangers, and why must it be done. Your first mail left a lot of explaining to be desired, a lot better now. Not need to begin ranting. -- Lgb
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
On Thu, Oct 09, 2003 at 11:12:46AM +0200, Lars Gullik Bjønnes wrote: | Debugging suggests that we have a problem with cursors accessing not | existing paragraphs. Looking at the code this might well be possible: If | the paragraph list is changed heavily (say assigned to) we invalidate | all iterators to it, most notably those hidden in the Cursors belonging | to the InsetText's LyXText. For smaller changes (say erasing of one | element), we invalidate only a few 'unlucky' iterators. Some times it | happens to work. But won't this be the case with offsets as well? Only get silent failure instead of crash, but the offset is still invalid. No. See below. | There are several places in the code where this is not taken care of | (most places actually), and frankly, I do neither want to figure out | where all of these places are nor do I want to add glue code 'just to | make it work' as long as there 'automatic' solutions. | One 'automatic' solution (and the simplest I can think of) is to use | offsets instead of iterators. These are stable, can be copied around | at will and checked for validity for each access if necessary. There is | neither glue code needed, and there is no need to hunt down and check | all occurences in the 'user code'. You cannot really check an offset for validity (except in a very few special cases). An offset is almost always valid even if it points to the wrong place. I can in some case, which happen to be most cases here: Most accesses go through LyXText::doSomething() (getPar() for instance). In these cases, we have access to the offset _and_ the paragraph list and can check e.g. for 0 = offset paragraph.size(). Moreover, we have now an 'uninitialized' value (-1, set in LyXCursor's default constructor) on which we can assert whenever we need a 'valid' cursor. The current problem is not just that the structures are broken, but that we are not able to tell when this happens. Early asserts would help much. Andre' -- Those who desire to give up Freedom in order to gain Security, will not have, nor do they deserve, either one. (T. Jefferson or B. Franklin or both...)
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
On Thu, Oct 09, 2003 at 11:14:04AM +0200, Lars Gullik Bjønnes wrote: What type does std::distance return? We should use that for the offsets. Some difference_type. I currently use typedef std::vectorchar::difference_type par_type; which is not _exactly_ what we need, but I've not seen any compiler implementation which is using different difference_type's for different containers. Andre'
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
On Thu, Oct 09, 2003 at 11:16:54AM +0200, Lars Gullik Bjønnes wrote: Your first mail left a lot of explaining to be desired, a lot better now. Not need to begin ranting. I'll try. Andre'
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
Andre Poenitz wrote: Nice numbers, but you miss the point. I am currently trying to fix crashs, not #includes.. No, I didn't miss the point. I was just being a pain in the ass. I'll try and stop that ;-) -- Angus
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
[EMAIL PROTECTED] (Lars Gullik Bjønnes) writes: | You are no way ahead of me. ^ w -- Lgb
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
Andre Poenitz [EMAIL PROTECTED] writes: | On Thu, Oct 09, 2003 at 11:14:04AM +0200, Lars Gullik Bjønnes wrote: What type does std::distance return? We should use that for the offsets. | Some difference_type. | I currently use | | typedef std::vectorchar::difference_type par_type; | which is not _exactly_ what we need, but I've not seen any compiler | implementation which is using different difference_type's for different | containers. Would it cost a lot to use the right one? and par_type is a bit anonymous... offset_type, offset_t ? -- Lgb
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
Andre Poenitz [EMAIL PROTECTED] writes: | On Thu, Oct 09, 2003 at 11:12:46AM +0200, Lars Gullik Bjønnes wrote: | Debugging suggests that we have a problem with cursors accessing not | existing paragraphs. Looking at the code this might well be possible: If | the paragraph list is changed heavily (say assigned to) we invalidate | all iterators to it, most notably those hidden in the Cursors belonging | to the InsetText's LyXText. For smaller changes (say erasing of one | element), we invalidate only a few 'unlucky' iterators. Some times it | happens to work. But won't this be the case with offsets as well? Only get silent failure instead of crash, but the offset is still invalid. | No. See below. | There are several places in the code where this is not taken care of | (most places actually), and frankly, I do neither want to figure out | where all of these places are nor do I want to add glue code 'just to | make it work' as long as there 'automatic' solutions. | One 'automatic' solution (and the simplest I can think of) is to use | offsets instead of iterators. These are stable, can be copied around | at will and checked for validity for each access if necessary. There is | neither glue code needed, and there is no need to hunt down and check | all occurences in the 'user code'. You cannot really check an offset for validity (except in a very few special cases). An offset is almost always valid even if it points to the wrong place. | I can in some case, which happen to be most cases here: Most accesses go | through LyXText::doSomething() (getPar() for instance). | In these cases, we have access to the offset _and_ the paragraph list and | can check e.g. for 0 = offset paragraph.size(). This is the special case I mentioned. You only check that the offset does not go off the end of the paragraphlist/paragraph. | Moreover, we have now an 'uninitialized' value (-1, set in LyXCursor's | default constructor) on which we can assert whenever we need a 'valid' | cursor. I wonder... would a more explicit uninitialized value be in order? boost::optionaloffset_t | The current problem is not just that the structures are broken, but that | we are not able to tell when this happens. Early asserts would help | much. Sure. -- Lgb
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
On Thu, Oct 09, 2003 at 11:27:10AM +0200, Lars Gullik Bjønnes wrote: Andre Poenitz [EMAIL PROTECTED] writes: | On Thu, Oct 09, 2003 at 11:14:04AM +0200, Lars Gullik Bjønnes wrote: What type does std::distance return? We should use that for the offsets. | Some difference_type. | I currently use | | typedef std::vectorchar::difference_type par_type; | which is not _exactly_ what we need, but I've not seen any compiler | implementation which is using different difference_type's for different | containers. Would it cost a lot to use the right one? Depends where we define it. If it stays in support/types.h we'd pull in std::listParagraph in BufferView_pimpl.h:#include support/types.h CutAndPaste.h:#include support/types.h InsetList.h:#include support/types.h ParagraphParameters.h:#include support/types.h ParameterStruct.h:#include support/types.h buffer.h:#include support/types.h bufferparams.h:#include support/types.h changes.h:#include support/types.h cursor.h:#include support/types.h lyxcursor.h:#include support/types.h lyxfind.h:#include support/types.h lyxrow.h:#include support/types.h lyxrow_funcs.h:#include support/types.h lyxtextclasslist.h:#include support/types.h paragraph.h:#include support/types.h paragraph_funcs.h:#include support/types.h sgml.h:#include support/types.h text_funcs.h:#include support/types.h which basically is 'everywhere'. Hmm... Ok. Clean solution: The list::difference_type is typedef typename Allocator::difference_type difference_type; The Allocator::difference_type is ptrdiff_t from cstddef So we'd jsut use a typedef of ptrdiff_t from cstddef. Happy? and par_type is a bit anonymous... offset_type, offset_t ? 'par_offset_type' perhaps? Andre'
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
On Thu, Oct 09, 2003 at 11:25:19AM +0200, Lars Gullik Bjønnes wrote: I wonder... would a more explicit uninitialized value be in order? boost::optionaloffset_t Please not. -1 is as explicit as we need it. Andre' -- Those who desire to give up Freedom in order to gain Security, will not have, nor do they deserve, either one. (T. Jefferson or B. Franklin or both...)
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
Andre Poenitz [EMAIL PROTECTED] writes: | Happy? pretty much. -- Lgb
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
Andre Poenitz <[EMAIL PROTECTED]> writes: | This is a patch to use 'par_type' offsets to ownerParagraphs().begin() | in LyXCursor. > | The drawback is obvious: we have O(n) access in some cases where we had | O(1) before. Only some cases? | However,I have not seen _any_ indication that this is | noticable after playing around with the UserGuide. > | In any case, the benefits seem to clearly outweigh this: LyXCursor is | now 'copiable' and we can add asserts to the 'getPar()' set of functions | to catch accesses to 'uninitialized' cursor data early. And we've lost a | few dependency on ParagraphList_fwd.h. I have no idea what 'copiable' is. The cursor is perfectly copiable with the iterator so what does this really change? -- Lgb
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
Andre Poenitz wrote: > And we've lost a few dependency on ParagraphList_fwd.h. which is a non-issue in my book since it drags in system files only. Ok, ok, so you don't like . I note that support/types.h still drags in . -- Angus
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
Angus Leeming <[EMAIL PROTECTED]> writes: | Andre Poenitz wrote: >> And we've lost a few dependency on ParagraphList_fwd.h. | which is a non-issue in my book since it drags in system files only. | Ok, ok, so you don't like . I note that support/types.h still | drags in . And I claim that you can drag in a bunch of headers without noticing any effect. Time to stop this header phobia. -- Lgb
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
Lars Gullik Bjønnes wrote:
> | Andre Poenitz wrote:
>>> And we've lost a few dependency on ParagraphList_fwd.h.
> | which is a non-issue in my book since it drags in system files
> | only. Ok, ok, so you don't like . I note that
> | support/types.h still drags in .
>
> And I claim that you can drag in a bunch of headers without noticing
> any effect.
>
> Time to stop this header phobia.
I agree, but only for system headers. Unnecessary project headers lead
to the re-compilation of unnecessarily large chunks of the tree each
time they are changed.
Anyway, let's see if we can back that up:
$ cat lars.C
#include
#include
#include
#include
int main() {
return 0;
}
$ time g++ -o lars lars.C
real0m0.684s
user0m0.420s
sys 0m0.030s
]$ cat andre.C
int main() {
return 0;
}
$ time g++ -o andre andre.C
real0m0.152s
user0m0.150s
sys 0m0.000s
Conclusion: dragging in those headers costs half a second.
$ cd lyx/devel/src && find . -name '*.C' | wc -l
818
Conclusion: the worst case is that this costs us 400secs on a full
compile.
--
Angus
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
On Thu, Oct 09, 2003 at 10:18:58AM +0200, Lars Gullik Bjønnes wrote: > Andre Poenitz <[EMAIL PROTECTED]> writes: > > | This is a patch to use 'par_type' offsets to ownerParagraphs().begin() > | in LyXCursor. > > > | The drawback is obvious: we have O(n) access in some cases where we had > | O(1) before. > > Only some cases? Nitpicking mode? No, not all accesses are O(n), and if the chage is propagated further it is to be expected that some of the current translations offset <-> iterator will be removed again. > | However,I have not seen _any_ indication that this is > | noticable after playing around with the UserGuide. > > > | In any case, the benefits seem to clearly outweigh this: LyXCursor is > | now 'copiable' and we can add asserts to the 'getPar()' set of functions > | to catch accesses to 'uninitialized' cursor data early. And we've lost a > | few dependency on ParagraphList_fwd.h. > > I have no idea what 'copiable' is. The cursor is perfectly copiable But not structures based on it. > with the iterator so what does this really change? InsetText is currently pretty fragile, most notably, copying does not work as e.g. the tabular code assumes. Debugging suggests that we have a problem with cursors accessing not existing paragraphs. Looking at the code this might well be possible: If the paragraph list is changed heavily (say assigned to) we invalidate all iterators to it, most notably those hidden in the Cursors belonging to the InsetText's LyXText. For smaller changes (say erasing of one element), we invalidate only a few 'unlucky' iterators. Some times it happens to work. There are several places in the code where this is not taken care of (most places actually), and frankly, I do neither want to figure out where all of these places are nor do I want to add glue code 'just to make it work' as long as there 'automatic' solutions. One 'automatic' solution (and the simplest I can think of) is to use offsets instead of iterators. These are stable, can be copied around at will and checked for validity for each access if necessary. There is neither glue code needed, and there is no need to hunt down and check all occurences in the 'user code'. Andre' -- Those who desire to give up Freedom in order to gain Security, will not have, nor do they deserve, either one. (T. Jefferson or B. Franklin or both...)
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
On Thu, Oct 09, 2003 at 09:31:13AM +, Angus Leeming wrote: > Andre Poenitz wrote: > > And we've lost a few dependency on ParagraphList_fwd.h. > which is a non-issue in my book since it drags in system files only. > Ok, ok, so you don't like . I note that support/types.h still > drags in . Those lost dependencies are not the reason for the patch, they are just a bonus. Andre' > -- Those who desire to give up Freedom in order to gain Security, will not have, nor do they deserve, either one. (T. Jefferson or B. Franklin or both...)
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
On Thu, Oct 09, 2003 at 10:46:56AM +0200, Lars Gullik Bjønnes wrote: > Angus Leeming <[EMAIL PROTECTED]> writes: > > | Andre Poenitz wrote: > >> And we've lost a few dependency on ParagraphList_fwd.h. > | which is a non-issue in my book since it drags in system files only. > | Ok, ok, so you don't like . I note that support/types.h still > | drags in . > > And I claim that you can drag in a bunch of headers without noticing > any effect. > > Time to stop this header phobia. H***, this is _no_ 'I don't like ' patch. This is preliminary work to fix these 'cri' bugs on bugzilla. I really don't know how one can make patches palatable to you. If it is small, it is not doing 'enough'. If it is big, it's doing too much. And there's, of course, that bit in between which is doing not enough while doing too much... Than there are speedup changes, which are not nice, and speed is not important anyway. There are changes _theoretically_ losing speed, which are not nice as we might lose performance, and performance is important. *sigh* Andre'
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
On Thu, Oct 09, 2003 at 09:55:32AM +, Angus Leeming wrote: > Conclusion: the worst case is that this costs us 400secs on a full > compile. Nice numbers, but you miss the point. I am currently trying to fix crashs, not #includes.. Andre' -- Those who desire to give up Freedom in order to gain Security, will not have, nor do they deserve, either one. (T. Jefferson or B. Franklin or both...)
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
Andre Poenitz <[EMAIL PROTECTED]> writes: | On Thu, Oct 09, 2003 at 10:18:58AM +0200, Lars Gullik Bjønnes wrote: >> Andre Poenitz <[EMAIL PROTECTED]> writes: >> >> | This is a patch to use 'par_type' offsets to ownerParagraphs().begin() >> | in LyXCursor. >> > >> | The drawback is obvious: we have O(n) access in some cases where we had >> | O(1) before. >> >> Only some cases? > | Nitpicking mode? Lack of information/description mode. | No, not all accesses are O(n), and if the chage is propagated further it | is to be expected that some of the current translations offset <-> | iterator will be removed again. > >> | However,I have not seen _any_ indication that this is >> | noticable after playing around with the UserGuide. >> > >> | In any case, the benefits seem to clearly outweigh this: LyXCursor is >> | now 'copiable' and we can add asserts to the 'getPar()' set of functions >> | to catch accesses to 'uninitialized' cursor data early. And we've lost a >> | few dependency on ParagraphList_fwd.h. >> >> I have no idea what 'copiable' is. The cursor is perfectly copiable > | But not structures based on it. > >> with the iterator so what does this really change? > | InsetText is currently pretty fragile, most notably, copying does not | work as e.g. the tabular code assumes. > | Debugging suggests that we have a problem with cursors accessing not | existing paragraphs. Looking at the code this might well be possible: If | the paragraph list is changed heavily (say assigned to) we invalidate | all iterators to it, most notably those hidden in the Cursors belonging | to the InsetText's LyXText. For smaller changes (say erasing of one | element), we invalidate only a few 'unlucky' iterators. Some times it | happens to work. But won't this be the case with offsets as well? Only get silent failure instead of crash, but the offset is still invalid. (In that it points somewhere else than intended.) | There are several places in the code where this is not taken care of | (most places actually), and frankly, I do neither want to figure out | where all of these places are nor do I want to add glue code 'just to | make it work' as long as there 'automatic' solutions. > | One 'automatic' solution (and the simplest I can think of) is to use | offsets instead of iterators. These are stable, can be copied around | at will and checked for validity for each access if necessary. There is | neither glue code needed, and there is no need to hunt down and check | all occurences in the 'user code'. You cannot really check an offset for validity (except in a very few special cases). An offset is almost always "valid" even if it points to the wrong place. -- Lgb
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
Andre Poenitz <[EMAIL PROTECTED]> writes: | On Thu, Oct 09, 2003 at 09:31:13AM +, Angus Leeming wrote: >> Andre Poenitz wrote: >> > And we've lost a few dependency on ParagraphList_fwd.h. >> which is a non-issue in my book since it drags in system files only. >> Ok, ok, so you don't like . I note that support/types.h still >> drags in . > | Those lost dependencies are not the reason for the patch, they are just | a bonus. What type does std::distance return? We should use that for the offsets. -- Lgb
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
Andre Poenitz <[EMAIL PROTECTED]> writes: | On Thu, Oct 09, 2003 at 10:46:56AM +0200, Lars Gullik Bjønnes wrote: >> Angus Leeming <[EMAIL PROTECTED]> writes: >> >> | Andre Poenitz wrote: >> >> And we've lost a few dependency on ParagraphList_fwd.h. >> | which is a non-issue in my book since it drags in system files only. >> | Ok, ok, so you don't like . I note that support/types.h still >> | drags in . >> >> And I claim that you can drag in a bunch of headers without noticing >> any effect. >> >> Time to stop this header phobia. > | H***, this is _no_ 'I don't like ' patch. Removing unneeded headers -> fine. Claiming that this is a bonus -> not. | This is preliminary work to fix these 'cri' bugs on bugzilla. > | I really don't know how one can make patches palatable to you. > | If it is small, it is not doing 'enough'. If it is big, it's doing too | much. And there's, of course, that bit in between which is doing not | enough while doing too much... > | Than there are speedup changes, which are not nice, and speed is not | important anyway. There are changes _theoretically_ losing speed, which | are not nice as we might lose performance, and performance is | important. > | *sigh* You are no way ahead of me. I am trying to fathom what this iterator -> offset change will really result in. Are there hidden dangers, and why must it be done. Your first mail left a lot of explaining to be desired, a lot better now. Not need to begin ranting. -- Lgb
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
On Thu, Oct 09, 2003 at 11:12:46AM +0200, Lars Gullik Bjønnes wrote: > | Debugging suggests that we have a problem with cursors accessing not > | existing paragraphs. Looking at the code this might well be possible: If > | the paragraph list is changed heavily (say assigned to) we invalidate > | all iterators to it, most notably those hidden in the Cursors belonging > | to the InsetText's LyXText. For smaller changes (say erasing of one > | element), we invalidate only a few 'unlucky' iterators. Some times it > | happens to work. > > But won't this be the case with offsets as well? Only get silent > failure instead of crash, but the offset is still invalid. No. See below. > | There are several places in the code where this is not taken care of > | (most places actually), and frankly, I do neither want to figure out > | where all of these places are nor do I want to add glue code 'just to > | make it work' as long as there 'automatic' solutions. > > > | One 'automatic' solution (and the simplest I can think of) is to use > | offsets instead of iterators. These are stable, can be copied around > | at will and checked for validity for each access if necessary. There is > | neither glue code needed, and there is no need to hunt down and check > | all occurences in the 'user code'. > > You cannot really check an offset for validity (except in a very few > special cases). An offset is almost always "valid" even if it points > to the wrong place. I can in some case, which happen to be most cases here: Most accesses go through LyXText::doSomething() (getPar() for instance). In these cases, we have access to the offset _and_ the paragraph list and can check e.g. for 0 <= offset < paragraph.size(). Moreover, we have now an 'uninitialized' value (-1, set in LyXCursor's default constructor) on which we can assert whenever we need a 'valid' cursor. The current problem is not just that the structures are broken, but that we are not able to tell when this happens. Early asserts would help much. Andre' -- Those who desire to give up Freedom in order to gain Security, will not have, nor do they deserve, either one. (T. Jefferson or B. Franklin or both...)
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
On Thu, Oct 09, 2003 at 11:14:04AM +0200, Lars Gullik Bjønnes wrote: > What type does std::distance return? We should use that for the > offsets. Some difference_type. I currently use typedef std::vector::difference_type par_type; which is not _exactly_ what we need, but I've not seen any compiler implementation which is using different difference_type's for different containers. Andre'
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
On Thu, Oct 09, 2003 at 11:16:54AM +0200, Lars Gullik Bjønnes wrote: > Your first mail left a lot of explaining to be desired, a lot better > now. Not need to begin ranting. I'll try. Andre'
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
Andre Poenitz wrote: > Nice numbers, but you miss the point. I am currently trying to fix > crashs, not #includes.. No, I didn't miss the point. I was just being a pain in the ass. I'll try and stop that ;-) -- Angus
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
[EMAIL PROTECTED] (Lars Gullik Bjønnes) writes: | You are no way ahead of me. ^ w -- Lgb
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
Andre Poenitz <[EMAIL PROTECTED]> writes: | On Thu, Oct 09, 2003 at 11:14:04AM +0200, Lars Gullik Bjønnes wrote: >> What type does std::distance return? We should use that for the >> offsets. > | Some difference_type. > | I currently use | | typedef std::vector::difference_type par_type; > | which is not _exactly_ what we need, but I've not seen any compiler | implementation which is using different difference_type's for different | containers. Would it cost a lot to use the right one? and par_type is a bit anonymous... offset_type, offset_t ? -- Lgb
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
Andre Poenitz <[EMAIL PROTECTED]> writes: | On Thu, Oct 09, 2003 at 11:12:46AM +0200, Lars Gullik Bjønnes wrote: >> | Debugging suggests that we have a problem with cursors accessing not >> | existing paragraphs. Looking at the code this might well be possible: If >> | the paragraph list is changed heavily (say assigned to) we invalidate >> | all iterators to it, most notably those hidden in the Cursors belonging >> | to the InsetText's LyXText. For smaller changes (say erasing of one >> | element), we invalidate only a few 'unlucky' iterators. Some times it >> | happens to work. >> >> But won't this be the case with offsets as well? Only get silent >> failure instead of crash, but the offset is still invalid. > | No. See below. > >> | There are several places in the code where this is not taken care of >> | (most places actually), and frankly, I do neither want to figure out >> | where all of these places are nor do I want to add glue code 'just to >> | make it work' as long as there 'automatic' solutions. >> > >> | One 'automatic' solution (and the simplest I can think of) is to use >> | offsets instead of iterators. These are stable, can be copied around >> | at will and checked for validity for each access if necessary. There is >> | neither glue code needed, and there is no need to hunt down and check >> | all occurences in the 'user code'. >> >> You cannot really check an offset for validity (except in a very few >> special cases). An offset is almost always "valid" even if it points >> to the wrong place. > | I can in some case, which happen to be most cases here: Most accesses go | through LyXText::doSomething() (getPar() for instance). > | In these cases, we have access to the offset _and_ the paragraph list and | can check e.g. for 0 <= offset < paragraph.size(). This is the special case I mentioned. You only check that the offset does not go off the end of the paragraphlist/paragraph. | Moreover, we have now an 'uninitialized' value (-1, set in LyXCursor's | default constructor) on which we can assert whenever we need a 'valid' | cursor. I wonder... would a more explicit "uninitialized" value be in order? boost::optional | The current problem is not just that the structures are broken, but that | we are not able to tell when this happens. Early asserts would help | much. Sure. -- Lgb
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
On Thu, Oct 09, 2003 at 11:27:10AM +0200, Lars Gullik Bjønnes wrote: > Andre Poenitz <[EMAIL PROTECTED]> writes: > > | On Thu, Oct 09, 2003 at 11:14:04AM +0200, Lars Gullik Bjønnes wrote: > >> What type does std::distance return? We should use that for the > >> offsets. > > > | Some difference_type. > > > | I currently use > | > | typedef std::vector::difference_type par_type; > > > | which is not _exactly_ what we need, but I've not seen any compiler > | implementation which is using different difference_type's for different > | containers. > > Would it cost a lot to use the right one? Depends where we define it. If it stays in support/types.h we'd pull in std::list in BufferView_pimpl.h:#include "support/types.h" CutAndPaste.h:#include "support/types.h" InsetList.h:#include "support/types.h" ParagraphParameters.h:#include "support/types.h" ParameterStruct.h:#include "support/types.h" buffer.h:#include "support/types.h" bufferparams.h:#include "support/types.h" changes.h:#include "support/types.h" cursor.h:#include "support/types.h" lyxcursor.h:#include "support/types.h" lyxfind.h:#include "support/types.h" lyxrow.h:#include "support/types.h" lyxrow_funcs.h:#include "support/types.h" lyxtextclasslist.h:#include "support/types.h" paragraph.h:#include "support/types.h" paragraph_funcs.h:#include "support/types.h" sgml.h:#include "support/types.h" text_funcs.h:#include "support/types.h" which basically is 'everywhere'. Hmm... Ok. Clean solution: The list::difference_type is typedef typename Allocator::difference_type difference_type; The Allocator::difference_type is ptrdiff_t from So we'd jsut use a typedef of ptrdiff_t from cstddef. Happy? > and par_type is a bit anonymous... offset_type, offset_t ? 'par_offset_type' perhaps? Andre'
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
On Thu, Oct 09, 2003 at 11:25:19AM +0200, Lars Gullik Bjønnes wrote: > I wonder... would a more explicit "uninitialized" value be in order? > > boost::optional Please not. -1 is as explicit as we need it. Andre' > -- Those who desire to give up Freedom in order to gain Security, will not have, nor do they deserve, either one. (T. Jefferson or B. Franklin or both...)
Re: [patch] store offset instead of ParagraphList::iterator in Cursor
Andre Poenitz <[EMAIL PROTECTED]> writes: | Happy? pretty much. -- Lgb
