kicad-developers team mailing list archive

[Andrew Lutsenko <anlutsenko@xxxxxxxxx>]

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>
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
> >>>> 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
> >>> 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
> Unsubscribe : https://launchpad.net/~kicad-developers
> More help   : https://help.launchpad.net/ListHelp
>