kicad-developers team mailing list archive

["Steven A. Falco" <stevenfalco@xxxxxxxxx>]

I'll look at that.  The worst burst of backspaces is about 7 characters long, so I could accumulate 14 chars or so before making a decision.  In other words, run a circular buffer, and when I see the first non-backspace after a string of backspaces, then process the buffer.

But I'm starting to think that the better approach is to drop this patch from the official tree, and just put my original patch into Fedora-only, as a temporary patch, to be removed when the library issue is corrected.

But I'll still play around with your idea to see how it looks once I get it working. :-)

	Steve

On 1/15/19 12:08 AM, Andrew Lutsenko wrote:
> Hi Steven,
> 
> Your code is slow because you are using O(n^2) algorithm (look up big O notation if you don't know what that means, tldr is that for 1mb string it will take on the order of 10^12 operations to process in the worst case where there are lots of '\b' characters).
> Instead of iteratively deleting all backspace characters in the string better approach is to gather all characters you want to keep in a buffer.
> For example (I haven't compiled this but should be close enough):
> 
> wxString buf;
> int c1, c2; // note the int type, it's important because wxStrings are unicode
> for(int i = 0; i + 1 < t.length(); i++) {
>   c1 = t[i];
>   c2 = t[i + 1]; 
>   if (c1 != '\b' && c2 != '\b')
>     buf.Append(wxUniChar(c1)); // Add current character unless it's backspace or next one is backspace
> }
> if (t.length() > 0 && c2 != '\b') // Add last character unless it's backspace
>   buf.Append(wxUniChar(c2));
> m_simConsole->AppendText( buf + "\n" );
> 
> This is O(n) as apposed to O(n^2) so it will be blink of an eye to process 1mb. If it is still slow than it's because operator[] on wxString is not constant time. In that case convert it to std::wstring first, which is guaranteed to have constant time random access in c++11.
> 
> Regards,
> Andrew
> 
> On Mon, Jan 14, 2019 at 5:58 PM Steven A. Falco <stevenfalco@xxxxxxxxx <mailto:stevenfalco@xxxxxxxxx>> wrote:
> 
>     Thanks, Wayne.  I'll read through that.
> 
>     As an experiment, I tried the code below, but it turns out to be far too slow to be usable.  What I've discovered is that all the "percent complete" status comes in as a single one+ megabyte string, so removing backspaces and the preceding characters one pair at a time is not workable.  Maybe there is a faster algorithm, but I'm not knowledgeable enough in C++ to write it.
> 
>     What I can say is that any event with a newline seems to come in separately, so there is no risk to losing valid output, as far as I can see.  Here is a screenshot: https://www.dropbox.com/s/gc21pjyujo4ao3c/Screenshot_20190114_183910.png?dl=0 where I print out the length of the string, then the string itself.  As you can see, each line is short, up until the megabyte line comes in.  You can see the length going down by 2 each time I remove a character-backspace pair.
> 
>     I don't know where this leaves us.  Someone could try to come up with an efficient way to filter out the backspaces, or we could go with my original approach, cleaned up to conform to the coding conventions.  Please advise.
> 
>             Steve
> 
>     void SIM_PLOT_FRAME::onSimReport( wxCommandEvent& aEvent )
>     {
>         wxString t = aEvent.GetString();
>         size_t position;
> 
>         while( ( position = t.find( "\b" ) ) != wxString::npos )
>         {
>             if( position >= 1 )
>             {
>                     t = t.Mid(0, position - 1) + t.Mid(position + 1);
>             }
>             else
>             {
>                     t = t.Mid(0, position) +  t.Mid(position + 1);
>             }
>         }
> 
>         m_simConsole->AppendText( aEvent.GetString() + "\n" );
>         m_simConsole->SetInsertionPointEnd();
>     }
> 
>     On 1/14/19 6:21 PM, Wayne Stambaugh wrote:
>     > On 1/14/19 1:06 PM, Steven A. Falco wrote:
>     >> The issue was discussed here:
>     >>
>     >> https://forum.kicad.info/t/trying-to-get-ngspice-working-on-fedora/14628
>     >>
>     >> If you tell me what my "coding policy errors" are, or point me to something I should read, then I can do better next time.
>     >
>     > http://docs.kicad-pcb.org/doxygen/md_Documentation_development_coding-style-policy.html
>     >
>     >>
>     >> I've attached a new copy of the patch - the code change is identical, the only difference is that it has the commit message prepended.
>     >>
>     >>      Steve
>     >>
>     >> On 1/14/19 12:50 PM, Wayne Stambaugh wrote:
>     >>> Steve,
>     >>>
>     >>> Please include the bug report link so I can link the patch to the bug
>     >>> report.  I'll fix the coding policy errors since I'm assuming this is as
>     >>> one a done patch for you.
>     >>>
>     >>> Tom or Orson,
>     >>>
>     >>> Any objections to this patch.  I didn't test it but on the surface it
>     >>> appears to resolve the issue.
>     >>>
>     >>> Cheers,
>     >>>
>     >>> Wayne
>     >>>
>     >>> On 1/14/2019 10:30 AM, Steven A. Falco wrote:
>     >>>> I wanted to close the loop on the SIGTRAP crash that I reported a few days ago.
>     >>>>
>     >>>> The issue is probably unique to Fedora, and stems from a huge quantity of "percent complete" messages that the ngspice library passes back to KiCad.  I'm not kidding when I say huge - it amounts to over 1 megabyte of text, including many backspace characters.  When I try to select the text, it probably blows up the clipboard and causes the crash.
>     >>>>
>     >>>> The ideal fix will be to have the Fedora ngspice maintainer remove a flag, which in turn will disable the "percent complete" messages.
>     >>>>
>     >>>> In the interim, I have a patch that filters out any line containing a string of backspaces.  I don't know if there is any interest in applying this patch to the official KiCad sources, but I've attached it here in case there is interest.  I see it as defensive programming. :-)
>     >>>>
>     >>>> I'll wait a bit to see what happens with the ngspice library.  If it looks like there will be a substantial delay in having the flag removed, I can always apply my patch and push that as the next official Fedora build.
>     >>>>
>     >>>>    Steve
>     >>>>
>     >>>> On 1/11/19 2:25 PM, Steven A. Falco wrote:
>     >>>>> On 1/11/19 1:51 PM, Steven A. Falco wrote:
>     >>>>>> On 1/11/19 1:21 PM, Seth Hillbrand wrote:
>     >>>>>>> Am 2019-01-11 12:18, schrieb Steven A. Falco:
>     >>>>>>>> I tried another ngspice experiment.  I ran a simulation, and it
>     >>>>>>>> worked, albeit with the data size warning I asked about earlier.  So
>     >>>>>>>> far so good.
>     >>>>>>>
>     >>>>>>> That warning was saying that it ran out of memory and had overwritten unplanned space.  I would expect a crash after that.  I'm not sure that KiCad can trap that kind of error as it occurred inside the library.
>     >>>>>>
>     >>>>>> Ok, but I'm concerned about the bug reports I'll get if I were to enable ngspice and push the build to the Fedora community.
>     >>>>>>
>     >>>>>> I'll wait to see if the forum has any thoughts on the warning.  I'll only enable ngspice in the official Fedora builds if I can get to where the examples run cleanly.
>     >>>>>
>     >>>>> I saved the netlist from the simple example I've been running:
>     >>>>>
>     >>>>> .title KiCad schematic
>     >>>>> V101 in 0 PULSE (0 5 1u 1u 1u 1 1)
>     >>>>> C101 Net-_C101-Pad1_ 0 1u
>     >>>>> C102 out 0 100n
>     >>>>> R101 Net-_C101-Pad1_ in 10k
>     >>>>> R102 out Net-_C101-Pad1_ 1k
>     >>>>> .save @v101[i]
>     >>>>> .save @c101[i]
>     >>>>> .save @c102[i]
>     >>>>> .save @r101[i]
>     >>>>> .save @r102[i]
>     >>>>> .save V(0)
>     >>>>> .save V(GND)
>     >>>>> .save V(Net-_C101-Pad1_)
>     >>>>> .save V(in)
>     >>>>> .save V(out)
>     >>>>> .tran 1u 100m
>     >>>>> .end
>     >>>>>
>     >>>>> When I run this circuit in stand-alone ngspice, it does a lot of overprinting, apparently to indicate the run-time of the job.  Here is a small example of the character stream, where there are tons of backspaces as part of the overprinting:
>     >>>>>
>     >>>>> saf$ od -c foo
>     >>>>> 0000000   %   0   .   0   0  \b  \b  \b  \b  \b   %   0   .   0   0  \b
>     >>>>> 0000020  \b  \b  \b  \b   %   0   .   0   0  \b  \b  \b  \b  \b   %   0
>     >>>>> 0000040   .   0   0  \b  \b  \b  \n
>     >>>>> 0000047
>     >>>>>
>     >>>>> The stand-alone captured output from this simple circuit is around 1 Mbyte!  I'm guessing that this huge amount of data is blowing up the window and showing all of the strange characters.
>     >>>>>
>     >>>>> I'm not sure of the division of labor here.  Is that something that a KiCad developer should address, or is it a library issue?  Hopefully there is a flag that can be passed to the library to suppress the overprinted text.
>     >>>>>
>     >>>>>   Steve
>     >>>>>
>     >>>>
>     >>>>
>     >>>> _______________________________________________
>     >>>> Mailing list: https://launchpad.net/~kicad-developers
>     >>>> Post to     : kicad-developers@xxxxxxxxxxxxxxxxxxx <mailto:kicad-developers@xxxxxxxxxxxxxxxxxxx>
>     >>>> Unsubscribe : https://launchpad.net/~kicad-developers
>     >>>> More help   : https://help.launchpad.net/ListHelp
>     >>>>
>     >>>
>     >>> _______________________________________________
>     >>> Mailing list: https://launchpad.net/~kicad-developers
>     >>> Post to     : kicad-developers@xxxxxxxxxxxxxxxxxxx <mailto:kicad-developers@xxxxxxxxxxxxxxxxxxx>
>     >>> Unsubscribe : https://launchpad.net/~kicad-developers
>     >>> More help   : https://help.launchpad.net/ListHelp
>     >>>
>     >>
>     >
> 
> 
>     _______________________________________________
>     Mailing list: https://launchpad.net/~kicad-developers
>     Post to     : kicad-developers@xxxxxxxxxxxxxxxxxxx <mailto:kicad-developers@xxxxxxxxxxxxxxxxxxx>
>     Unsubscribe : https://launchpad.net/~kicad-developers
>     More help   : https://help.launchpad.net/ListHelp
>