Re: Optimized implementation of AC and AC_Q pattern matching algorithms

[abed mohammad kamaluddin <abedamu () gmail com>]

Hi Hui,

I have compiled using default options - i.e. using -O2 flag for running on
Intel Machines, no other specific option and it is easily reproducible. For
other processors we use some processor-specific flags.

For profiling I used in-house proprietary profiling tools. I used both daq
pcap as well as network traffic generated using our own traffic generators.
However I feel any traffic which passes through ac/ac-q should give same
results.


Regards
--
Abed M K
Software Engineer
Cavium IDC

On Fri, Jan 25, 2013 at 9:10 PM, Hui Cao <hcao () sourcefire com> wrote:

> Hi Abed,
>
> Thanks for the patch. I will create a bug to track this.
>
> What's the compiling option for your testing? How did you profiling
> the performance? Knowing those might help us verify the performance
> gains.
>
> Thanks,
> Hui.
>
> On Fri, Jan 25, 2013 at 9:59 AM, abed mohammad kamaluddin
> <abedamu () gmail com> wrote:
> > Hi,
> >
> > I have been working on porting snort to multicore MIPs (Octeon)
> processors
> > for high performance networks for which I have analyzed the existing
> > software pattern matching algorithms. Even though the focus is on using
> our
> > own proprietary hardware pattern matching engine (which gives more than
> > double the performance of the best software algorithm), we are supporting
> > all s/w algorithms on our port.
> >
> > While profiling Aho-Corasick based search (ac and ac-q) , it was found
> that
> > the number of instructions could be significantly reduced in the main
> loop
> > (the AC_SEARCH macros) if the next state was pre-fetched before it was
> used.
> > Each byte of Input passes through this loop, so the performance increase
> is
> > significant w.r.t to the present implementation. Unexpectedly the gcc
> > compiler is unable to perform this optimization on its own.
> >
> > Though simple optimization, it translates into more than 10-14%
> performance
> > jump. Also, this is not processor specific. I have tried on both 2U Dual
> > Intel Xeon Server and OCTEON68XX (32 core CAVIUM processor) for above
> 20Gbps
> > line rates and I see the bump up. Also the same behavior is observed for
> > snort-2.9.0 to snort-2.9.4.
> >
> > I am attaching the patch (w.r.t snort 2.9.4) , and would like to
> contribute
> > the same to OSS community.
> >
> >
> > Regards
> > --
> > Abed M K
> > Software Engineer
> > Cavium IDC
> ------------------------------------------------------------------------------
> > Master Visual Studio, SharePoint, SQL, ASP.NET, C# 2012, HTML5, CSS,
> > MVC, Windows 8 Apps, JavaScript and much more. Keep your skills current
> > with LearnDevNow - 3,200 step-by-step video tutorials by Microsoft
> > MVPs and experts. ON SALE this month only -- learn more at:
> > http://p.sf.net/sfu/learnnow-d2d
> > _______________________________________________
> > Snort-devel mailing list
> > Snort-devel () lists sourceforge net
> > https://lists.sourceforge.net/lists/listinfo/snort-devel
> > Archive:
> > http://sourceforge.net/mailarchive/forum.php?forum_name=snort-devel
> >
> > Please visit http://blog.snort.org for the latest news about Snort!
------------------------------------------------------------------------------
Master Visual Studio, SharePoint, SQL, ASP.NET, C# 2012, HTML5, CSS,
MVC, Windows 8 Apps, JavaScript and much more. Keep your skills current
with LearnDevNow - 3,200 step-by-step video tutorials by Microsoft
MVPs and experts. ON SALE this month only -- learn more at:
http://p.sf.net/sfu/learnnow-d2d

_______________________________________________
Snort-devel mailing list
Snort-devel () lists sourceforge net
https://lists.sourceforge.net/lists/listinfo/snort-devel
Archive:
http://sourceforge.net/mailarchive/forum.php?forum_name=snort-devel

Please visit http://blog.snort.org for the latest news about Snort!