\d less efficient than [0-9] • Hacker News Board

Re: \d less efficient than [0-9]

#71

Post by stephencanon » Mon, May 20, 2013, 2:48 PM UTC

scott_s wrote: post #69

stephencanon wrote: post #63

Earlier quoted context omitted.

Those events are all on the order of micro-seconds, far shorter than the benchmark duration. A tenth of a second is an eternity on a modern CPU.

One of those events, yes. But it's possible for the system to be experiencing a bursty workload unrelated to your benchmark, and many of those events may happen. There's also the problems of startup effects, both at the high level (the VM, which in this case is .Net), the medium level (major and minor page faults) and the low level (caches). My rule of thumb is that benchmarks which are supposed to be bound by the pr…

VM startup effects I can get behind as a confound; page faults and cache effects are below millisecond level (filling the beefiest Sandybridge Xeon L3 cache you can buy from a completely cold state is on the order of 1 millisecond, and a micro benchmark like this doesn’t come close to using that much data).

I would also note that one is sometimes in the position of needing to measure performance of a compute-intensive task that is latency-critical but will not be running constantly; in such a scenario, using long-running benchmarks can be misleading because the processor will become thermally constrained and drop in and out of lower voltage/frequency bands, further confounding measurements.

I agree with you that a tenth of a second is on the shorter side of what I would like to see in such a benchmark, but I don’t think the situation is as dire as your first post suggested; unless the system is exceptionally noisy, the measurements seem to be valid, despite the relatively short duration. 60 seconds is overkill for a simple task like this.

Re: \d less efficient than [0-9]

#72

Post by trebor » Mon, May 20, 2013, 2:56 PM UTC

0x0 wrote: post #10

I wonder what kind of security vulnerabilities could be looming in validators not expecting non-ascii 0-9 digits and using this regex?

As of PHP 5.3, PHP-powered software is safe. Using

    is_numeric('١٣٦٨') // -> false
    preg_match('/\d/', '١٣٦٨') // -> no match / false
    filter_var('١٣٦٨', FILTER_VALIDATE_INT) // -> false

Which I'm thankful for. I should hope that most people understand base-10 and ascii numbers. I don't want to have to worry about properly validating/handling unicode characters with number parsing.

Re: \d less efficient than [0-9]

#73

Post by 0x0 » Mon, May 20, 2013, 3:19 PM UTC

trebor wrote: post #72

0x0 wrote: post #10

I wonder what kind of security vulnerabilities could be looming in validators not expecting non-ascii 0-9 digits and using this regex?

As of PHP 5.3, PHP-powered software is safe. Using is_numeric('١٣٦٨') // -> false preg_match('/\d/', '١٣٦٨') // -> no match / false filter_var('١٣٦٨', FILTER_VALIDATE_INT) // -> false Which I'm thankful for. I should hope that most people understand base-10 and ascii numbers. I don't want to have to worry about properly validating/handling unicode characters with number parsing.

In PHP 5.4.15, I get:

  var_dump(preg_match('/\d/u', '١٣٦٨')) -> 1
  var_dump(preg_match('/\d/', '١٣٦٨'))  -> 0

Re: \d less efficient than [0-9]

#74

Post by scott_s » Mon, May 20, 2013, 3:41 PM UTC

stephencanon wrote: post #71

scott_s wrote: post #69

Earlier quoted context omitted.

One of those events, yes. But it's possible for the system to be experiencing a bursty workload unrelated to your benchmark, and many of those events may happen. There's also the problems of startup effects, both at the high level (the VM, which in this case is .Net), the medium level (major and minor page faults) and the low level (caches). My rule of thumb is that benchmarks which are supposed to be bound by the pr…

VM startup effects I can get behind as a confound; page faults and cache effects are below millisecond level (filling the beefiest Sandybridge Xeon L3 cache you can buy from a completely cold state is on the order of 1 millisecond, and a micro benchmark like this doesn’t come close to using that much data). I would also note that one is sometimes in the position of needing to measure performance of a compute-intensiv…

Again, it's repeated page faults and cache effects.

When you run experiments, you want to draw conclusions. To have confidence in your conclusions, you want to eliminate as many variables as possible. In my work, I set the time of the benchmark high enough that I am confident that it is very unlikely for these effects to have a significant influence on the results. When you're drawing conclusions and publishing the results that will be scrutinized by peers, "overkill" is the way to go.

Also note that I was not the first poster on this subject.

Re: \d less efficient than [0-9]

#75

Post by stephencanon » Mon, May 20, 2013, 4:10 PM UTC

scott_s wrote: post #74

stephencanon wrote: post #71

Earlier quoted context omitted.

VM startup effects I can get behind as a confound; page faults and cache effects are below millisecond level (filling the beefiest Sandybridge Xeon L3 cache you can buy from a completely cold state is on the order of 1 millisecond, and a micro benchmark like this doesn’t come close to using that much data). I would also note that one is sometimes in the position of needing to measure performance of a compute-intensiv…

Again, it's repeated page faults and cache effects. When you run experiments, you want to draw conclusions. To have confidence in your conclusions, you want to eliminate as many variables as possible. In my work, I set the time of the benchmark high enough that I am confident that it is very unlikely for these effects to have a significant influence on the results. When you're drawing conclusions and publishing the r…

You cannot eliminate confounds by simple over-measurement. “Overkill” provides false confidence.

The only way to eliminate confounds is to understand them, and either control for them or bound them to an acceptable error tolerance. For a simple benchmark such as this, cache misses and page faults reach steady state within the first millisecond of operation; the error they contribute to the measurement of a .1s benchmark (even in aggregate) is no more than 1% — almost surely acceptable.

I have no experience with .Net, and would not care to make any estimates on the contribution of VM startup time, but the experiment in question does not include the VM startup in the measurement.

If a system were so noisy as to have interrupt storms on the order of .1s, then I would not be comfortable with timings that run for 60s either. I would much rather have statistics on 100 measurements of .1s each, which would make clear the impact of such anomalies (while still being faster to gather). There are many events that can make such measurements slower, but almost none that can make them faster; the distribution of the measurements is typically well-modeled by a Poisson distribution with bias. If one is actually trying to eliminate the effect of those events from the measurement, taking the minimum over many short samples is actually much closer to the truth than averaging over one long sample. If instead one is trying to include the effect of such events, then a different statistic would be in order.

Re: \d less efficient than [0-9]

#76

Post by nspragmatic » Mon, May 20, 2013, 4:40 PM UTC

ars wrote: post #5

wging wrote: post #3

Earlier quoted context omitted.

...at least in C# regexes.

Anyone know if this happens in other languages?

It happens in Objective-C:

    NSString *pattern = @"\\d", *string = @"੧";
    NSRegularExpression *regex = [NSRegularExpression regularExpressionWithPattern:pattern
                                                                           options:NSRegularExpressionCaseInsensitive
                                                                             error:nil];

    NSUInteger numMatches = [regex numberOfMatchesInString:string
                                                   options:0
                                                     range:NSMakeRange(0, [string length])];

    numMatches ? NSLog(@"%@ found by %@", string, pattern) : NSLog(@"%@ not found", string);

    // 2013-05-20 09:38:42.650 Regexperiment[17848:c07] ੧ found by \d

Re: \d less efficient than [0-9]

#77

Post by rhizome » Mon, May 20, 2013, 6:22 PM UTC

conroe64 wrote: post #49

rhizome wrote: post #48

Earlier quoted context omitted.

Use the s/, Luke s/^\s+?(.*)\s+?$/$1/g

That wouldn't work. First, it will only grab at only one whitespace character at the beginning and at the end. Second, if there was whitespace at the beginning or the end but not both, it won't match at all. "^\s* (.* ?)\s* $/$1/g" would work.

point being: get rid of the anchors in the alternation.

Re: \d less efficient than [0-9]

#78

Post by pfedor » Mon, May 20, 2013, 6:30 PM UTC

jeltz wrote: post #20

ars wrote: post #5

Earlier quoted context omitted.

Anyone know if this happens in other languages?

Happens in Perl but not ruby or PostgreSQL.

Doesn't happen in Perl for me:

  pfedor@Pawels-iMac:~$ perl -ne 'print "Digit!\n" if /\d/'
  af
  3
  Digit!
  23fa3
  Digit!
  asdf
  ١٢٣٤٥٦٧٨٩۰۱۲۳۴۵۶۷۸۹
  ৩৪৫৬৭৮৯੦੧੨੩੪੫੬੭੮੯૦૧૨૩૪૫
  ୧୨୩୪୫୬୭୮
  ౨౩౪౫౬౭౮౯೦೧೨೩೪೫೬೭೮೯൦൧൨൩൪൫൬൭൮൯๐๑๒๓๔๕๖๗๘๙໐໑໒໓
  234
  Digit!

(perl from Macports and perl from /usr/bin/perl behave the same in this respect.)

Re: \d less efficient than [0-9]

#79

Post by xonea » Mon, May 20, 2013, 10:18 PM UTC

pfedor wrote: post #78

jeltz wrote: post #20

Earlier quoted context omitted.

Happens in Perl but not ruby or PostgreSQL.

Doesn't happen in Perl for me: pfedor@Pawels-iMac:~$ perl -ne 'print "Digit!\n" if /\d/' af 3 Digit! 23fa3 Digit! asdf ١٢٣٤٥٦٧٨٩۰۱۲۳۴۵۶۷۸۹ ৩৪৫৬৭৮৯੦੧੨੩੪੫੬੭੮੯૦૧૨૩૪૫ ୧୨୩୪୫୬୭୮ ౨౩౪౫౬౭౮౯೦೧೨೩೪೫೬೭೮೯൦൧൨൩൪൫൬൭൮൯๐๑๒๓๔๕๖๗๘๙໐໑໒໓ 234 Digit! (perl from Macports and perl from /usr/bin/perl behave the same in this respect.)

You have to tell to interpret stdin as UTF-8 (flag -C) - then it works: https://news.ycombinator.com/item?id=5734641

Re: \d less efficient than [0-9]

#80

Post by pfedor » Tue, May 21, 2013, 2:06 AM UTC

xonea wrote: post #79

pfedor wrote: post #78

Earlier quoted context omitted.

Doesn't happen in Perl for me: pfedor@Pawels-iMac:~$ perl -ne 'print "Digit!\n" if /\d/' af 3 Digit! 23fa3 Digit! asdf ١٢٣٤٥٦٧٨٩۰۱۲۳۴۵۶۷۸۹ ৩৪৫৬৭৮৯੦੧੨੩੪੫੬੭੮੯૦૧૨૩૪૫ ୧୨୩୪୫୬୭୮ ౨౩౪౫౬౭౮౯೦೧೨೩೪೫೬೭೮೯൦൧൨൩൪൫൬൭൮൯๐๑๒๓๔๕๖๗๘๙໐໑໒໓ 234 Digit! (perl from Macports and perl from /usr/bin/perl behave the same in this respect.)

You have to tell to interpret stdin as UTF-8 (flag -C) - then it works: https://news.ycombinator.com/item?id=5734641

Good to know, thanks.

I'd argue that perl gets it right--as the default behavior, this behavior would gravely violate the principle of least surprise, but for the 0.01% of people who want \d to match ੧, there's no harm to making it available as an option you need to specifically request.