8 ms·

Probably just getting triggering excessive backtracking on some regex.

KMag 4y ago
Ironic, from the authors of RE2. They know the correct way to implement regexes. Though, when I worked on Google's indexing system, some researchers were having machine learning generate regexes to run on every page in the visible web... and mis-implemented the feature to re-compile the regex to DFA (which re2 effectively lazily converts to NFA via memoization) for every single page load. The speed of the indexing system dropped in half one day, and <Edit: Name Witheld> dug into it. <Name Withheld> took the gperf graph showing the giant node for regex compilation and wrote a savage meme "Your mother doesn't work here. Optimize your own code.", and sent it out to the researchers in question and also the indexing team. Maybe 6 months earlier, I cut into the same researchers for writing and approving C++ header file changes that defined (and leaked) macros "DO" for "{" and "OD" for "}" so that they could write C++ a bit more like Bash. As I remember, the macro leak for DO caused compilation errors in SpiderMonkey, which I fixed. After fixing the breakage, I just left an extra comment on the code review "Really? Leaking DO and OD macros to avoid typing curly braces?" without emailing any lists. They were really embarrassed removed DO and OD within a couple of days, and <Name Withheld> didn't know that I had laid into them a bit 6 months earlier. (I had implemented some very coarse-grained super-lightweight type-based data flow analysis into SpiderMonkey, which is why some of the Google headers were being included while compiling SpiderMonkey.)
- haliskerbas 4y ago
  Some people might get off on that kind of culture. But this story makes me glad I don’t work there for some reason.
  - KMag 4y ago
    There's a good deal of responsibility in writing code that is going to run over every single page (and PDF document, MS Word doc, the higher ranked Flash animations, etc.) in the visible web. For my part, I once made a bad assumption about how the Google SAX-style parser handled callbacks for zero-length XHTML start-stop tags. I presumed that <title/> would get a callback with the end-of-open-tag and start-of-close-tag pointers being equal, at the character after the close of the tag. Instead, the parser called the callback with the start-of-close-tag pointer after the start-of-close-tag pointer. (I had misinterpreted the API as passing pointers to the start and end of enclosed content.) I had test cases for un-closed <title> tags and <title></title>... but when my code hit production, the few pages (fewer than 1 in a million) that expressed an empty title as <title/> caused my code to try and construct a string with negative length and crashed that portion of the indexing system. I was right to feel very embarrassed for my oversight. I remember the savage meme so clearly because it was quite out of the norm, and I felt bad for the guys since they were so quick to fix things even when not publicly shamed. (Only the author and reviewer got notified when I left a comment on their code review.)
    - cscurmudgeon 4y ago
      Really? Is there any science showing rude reviews improve some metric or some greater good?
      - KMag 4y ago
        It wasn't the best way to criticize the code review. If I could go back in time 15 years, it's also not the first mistake I would fix. It stuck in my mind because I felt bad about it. I was frustrated that I had been hounded to drop what I was doing and fix the build because of clear style guide violations that a reviewer let slip. (A couple years later, Google implemented every commit getting a full compilation and run of all tests that code-coverage showed affected the covered code. These days, I wouldn't have been hounded to fix a build break caused by someone else.)
    - jolux 4y ago
      What does it mean that you were right to feel embarrassed? You were wrong to make the mistake, sure, but that happens. That’s what a mistake is. It’s not clear to me what shame helps in this instance. If somebody has a pattern of not meeting a quality bar with their code that’s one thing, but otherwise cutting people up for mistakes really seems like bad culture. Aren’t you supposed to practice blameless postmortems and all that at Google?
      - wutbrodo 4y ago
        My recollection from my time there, as well as one of the biggest cultural differences noticeable between my and my workplaces since, is that big chunks of the company really do believe in the blameless postmortem ideal. But culture isn't a magic tool that completely neutralizes assholes, and there are assholes in _every_ organization of sufficient size, like the "[name redacted]" character in the previous post
        KMag 4y ago
        I probably should have left [redacted]'s name out of it. He's a nice guy, but a bit cynical and rough on the edges, at least he was 15 years ago. He fit in well in New York, brutally honest, but actually generally nice. Edit: I should point out that we were in Google NYC, as were the researchers. We had lunch with them some times. I remember the first name and face of the guy who submitted the slow code, but forget his family name and intentionally left his name out. New Yorker to New Yorker adds a lot of context. Google's corporate culture is generally very Californian, but this happened all within the New York office between people who generally got along pretty well and knew each other decently. In context, there was a heavy note of respect for someone's abilities and disappointment that they weren't performing at a top level. He wouldn't have been so harsh with someone who was new or was a weaker engineer, or someone who wasn't used to New York culture.
  - a-dub 4y ago
    having spent time on both sides of the fence, i've noticed that there can be a rivalry of sorts between software engineers and ml/ds/researcher types. researcher types often get to work on problems that swe types find interesting, so some swes get grumbly. researcher types also tend to write pretty horrific code which adds salt to the wounds. but there also can be a sort of envy that emanates from the research side. many are fully aware of their shortcomings and are envious of the swes ability to get things done on computers cleanly. it often seems that there can be yearning to wear each other's hats from the two groups. if i were running a company i think i'd try to break down that wall as it would probably make a lot of people happier. of course, the right answer here isn't a meme... it's performance regression tests in the ci suite. and maybe a little training on why customizing a programming language with macros is bad.
    - KMag 4y ago
      > maybe a little training on why customizing a programming language with macros is bad Both the author and the reviewer had passed C++ style certification. They knew why it was bad. They just got a little lazy and wanted to write their code in a way that felt familiar to them, and figured it was harmless. I got a bit grumpy at having to drop what I was doing right away to fix their mistake due to their laziness.
      - a-dub 4y ago
        also, just to be clear. the macro only included open and close curlies? if so that's silly, as it is literally 2x the work to type. if they also included some sort of state that had to be managed, then it starts to verge towards reasonable.
        KMag 4y ago
        I think that maybe the author felt like finding the end of a loop stood out much better that way, instead of trying to distinguish the ends of conditional blocks from the ends of loops. If you're used to poorly formatted code in an ML PhD program, it does make some sense. I've worked with a bit of academic Fortran code for my mechanical engineering degree and can sympathize. Also, D and O are shorter reaches on the keyboard than { and }. Yes, "OD" was definitely just "}". DO might have been ") {" to allow while (a < b DO ... OD
  - jiggawatts 4y ago
    Conversely I would prefer to work in a place like that. Professionalism at scale isn’t achievable by tolerating idiotic behaviour and being nice to everyone no matter how dangerously stupid they are being. There is a point where someone has to put their foot down and demand things be done properly, otherwise the inevitable consequence is a giant mess leading to disaster. You might be used to small startup teams with responsible, experienced developers. Out there in larger industry you get people doing absolutely crazy things that break huge, expensive systems. There’s a difference between “oops I didn’t realise this library doesn’t scale the way I assumed it did” and “rewriting language symbols because I’m too stupid to use more than one syntax forever and ever.” The standard you walk past is the standard you accept. Are you saying you would walk past C code with DO…OD instead of {…}? Would you accept that standard just to be “nice” all the time?
    - runlevel1 4y ago
      There was a time when I would have agreed with that. What I've learned since then is that, with a healthy company culture, you can give frank feedback -- even about stupid mistakes -- without it being a rebuke. It's also important that you target the right problem. It's only human for smart people do stupid things sometimes. In the specific DO...OD example, I'd be more interested in how it got through a code review than the mistake itself. (Funny enough, early versions of the C source for Bash itself had macros like that.) Now, if someone exhibits a pattern of ignoring good, constructive feedback, that's a problem. The folks I've seen like that both gave terrible feedback and took feedback terribly. That's a behavioral problem, and you only get so many chances to correct that before it's time for them to find other employment.
    - jseban 4y ago
      > There is a point where someone has to put their foot down and demand things be done properly, otherwise the inevitable consequence is a giant mess leading to disaster. This is what management is for, too bad tech companies are too cool for that and prefer to live out lord of the flies.
      - alasdair_ 4y ago
- Alex3917 4y ago
  Re2 is also slower, so they might not be using it for high volume stuff. Also I’ve heard that Google automatically fails people who use regex in interviews, so their average engineers probably aren’t the best at it.
  - KMag 4y ago
    > Also I’ve heard that Google automatically fails people who use regex in interviews, Hmm... I don't remember that, and I conducted over 100 interviews back when I was at Google. A blanket failure for using a regex sounds like it's missing some nuance. But, maybe that was before or after my time. I wouldn't be surprised if they start out with some interview questions that are easy to implement as regexes, but then gradually make the question harder and more general, where a pushdown automaton is necessary for a general correct solution, and fail people who either don't get a correct answer or end up implementing a pushdown automaton by dynamically generating larger and larger regexes.
    - Alex3917 4y ago
      I think it's more that you need to give the O(n) of your answer, which is generally very difficult to do with regex. And even if it's possible, it might not be an acceptable O(n). In general regexes finish instantly for normal sized inputs, but the actual O(n) might be quadratic or whatever.
- vl 4y ago
  But why it even happened? Typically you run Flume over docjoins in your project’s quota. If you screw up, all that should happen is that your Flume job is out of quota.
  - KMag 4y ago
    This was in the Borg days, pre-Flume. As I remember, we had at least one Borg cluster to ourselves for indexing. Our quota was a cluster. We cared because indexing latency is important. Engineers get paged and woken up in the middle of the night when indexing latency gets high. Doubling CPU usage meant doubling indexing latency. The pre-Percolator indexing system ran roughly 1,000 threads per box on roughly 1,000 Warp18 boxes. Of course, most of those threads were blocked on I/O. (Warp18 was something like 16 cores per box... I think those were the RevE Opterons that had the memory fence bug that caused the glibc semaphore implementation to not actually synchronize operations.) I personally would have written things using more async and/or non-blocking I/O, but the main reasoning in Google at the time was that massively multithreaded blocking I/O is a simpler programming model and closer to what was being taught in school those days. Also, the indexing system's quota is huge. Someone made a mistake in their benchmark program that they thought got maximum utilization out of the Warp18 hardware. The indexing system actually got higher utilization than the hardware stress-test, resulting in cooling being under-provisioned in the Atlanta datacener (more than a decade ago, I'm sure indexing has moved now). There was a couple day stretch one hot Summer where we needed to stay on the phone with staff inside the Atlanta DC to keep track of the temperature inside the datacenter. When the temperatures started to get above something like 80 F, we needed to dial back on the number of workers in our Borg jobs. While testing the prototype for the Percolator indexing system, we were luckily sitting right next to an engineer who planned datacenters. We luckily overheard him saying he couldn't figure out why the power usage seemed to be swinging so wildly. It was literally the power usage of a decent sized town suddenly ramping up and down. We asked him the exact times power usage was ramping up and down, and figured out it was when Frank and Daniel were starting and stopping the Percolator prototype. My best guess is that the indexing system right before Percolator was a bit more energy efficient than Percolator, but maybe not. In any case, doubling CPU usage was a big deal. Real money, and in Atlanta, probably real carbon footprint. (The Dales was hydro, but I don't think much of Atlanta's power was renewable at that time.)
- rad_gruchalski 4y ago
  > Ironic, from the authors of RE2. They know the correct way to implement regexes. > Probably… Conclusions.
- dllthomas 4y ago
  > "DO" for "{" and "OD" for "}" so that they could write C++ a bit more like Bash. Bash (like Bourne shell before it) uses do/done. I think DO/OD was in an Algol (68?). I'm not sure where else? Bash does do the reversing for if/fi and case/esac, though.
  - fanf2 4y ago
    Steve Bourne wanted to use `od` to match Algol 68, but there was already an `od` utility for printing octal dumps. The original bournegol macros for DO and OD were a bit different: #define DO ){ #define OD ;} https://www.tuhs.org/cgi-bin/utree.pl?file=V7/usr/src/cmd/sh/mac.h https://www.tuhs.org/cgi-bin/utree.pl?file=V7/usr/src/cmd/sh...
ikiris 4y ago
You just triggered probably 50 sres involved in this bug.

KMag 4y ago

Ironic, from the authors of RE2. They know the correct way to implement regexes. Though, when I worked on Google's indexing system, some researchers were having machine learning generate regexes to run on every page in the visible web... and mis-implemented the feature to re-compile the regex to DFA (which re2 effectively lazily converts to NFA via memoization) for every single page load. The speed of the indexing system dropped in half one day, and <Edit: Name Witheld> dug into it. <Name Withheld> took the gperf graph showing the giant node for regex compilation and wrote a savage meme "Your mother doesn't work here. Optimize your own code.", and sent it out to the researchers in question and also the indexing team. Maybe 6 months earlier, I cut into the same researchers for writing and approving C++ header file changes that defined (and leaked) macros "DO" for "{" and "OD" for "}" so that they could write C++ a bit more like Bash. As I remember, the macro leak for DO caused compilation errors in SpiderMonkey, which I fixed. After fixing the breakage, I just left an extra comment on the code review "Really? Leaking DO and OD macros to avoid typing curly braces?" without emailing any lists. They were really embarrassed removed DO and OD within a couple of days, and <Name Withheld> didn't know that I had laid into them a bit 6 months earlier. (I had implemented some very coarse-grained super-lightweight type-based data flow analysis into SpiderMonkey, which is why some of the Google headers were being included while compiling SpiderMonkey.)

haliskerbas 4y ago
Some people might get off on that kind of culture. But this story makes me glad I don’t work there for some reason.
- KMag 4y ago
  There's a good deal of responsibility in writing code that is going to run over every single page (and PDF document, MS Word doc, the higher ranked Flash animations, etc.) in the visible web. For my part, I once made a bad assumption about how the Google SAX-style parser handled callbacks for zero-length XHTML start-stop tags. I presumed that <title/> would get a callback with the end-of-open-tag and start-of-close-tag pointers being equal, at the character after the close of the tag. Instead, the parser called the callback with the start-of-close-tag pointer after the start-of-close-tag pointer. (I had misinterpreted the API as passing pointers to the start and end of enclosed content.) I had test cases for un-closed <title> tags and <title></title>... but when my code hit production, the few pages (fewer than 1 in a million) that expressed an empty title as <title/> caused my code to try and construct a string with negative length and crashed that portion of the indexing system. I was right to feel very embarrassed for my oversight. I remember the savage meme so clearly because it was quite out of the norm, and I felt bad for the guys since they were so quick to fix things even when not publicly shamed. (Only the author and reviewer got notified when I left a comment on their code review.)
  - cscurmudgeon 4y ago
    Really? Is there any science showing rude reviews improve some metric or some greater good?
    - KMag 4y ago
      It wasn't the best way to criticize the code review. If I could go back in time 15 years, it's also not the first mistake I would fix. It stuck in my mind because I felt bad about it. I was frustrated that I had been hounded to drop what I was doing and fix the build because of clear style guide violations that a reviewer let slip. (A couple years later, Google implemented every commit getting a full compilation and run of all tests that code-coverage showed affected the covered code. These days, I wouldn't have been hounded to fix a build break caused by someone else.)
  - jolux 4y ago
    What does it mean that you were right to feel embarrassed? You were wrong to make the mistake, sure, but that happens. That’s what a mistake is. It’s not clear to me what shame helps in this instance. If somebody has a pattern of not meeting a quality bar with their code that’s one thing, but otherwise cutting people up for mistakes really seems like bad culture. Aren’t you supposed to practice blameless postmortems and all that at Google?
    - wutbrodo 4y ago
      My recollection from my time there, as well as one of the biggest cultural differences noticeable between my and my workplaces since, is that big chunks of the company really do believe in the blameless postmortem ideal. But culture isn't a magic tool that completely neutralizes assholes, and there are assholes in _every_ organization of sufficient size, like the "[name redacted]" character in the previous post
      - KMag 4y ago
        I probably should have left [redacted]'s name out of it. He's a nice guy, but a bit cynical and rough on the edges, at least he was 15 years ago. He fit in well in New York, brutally honest, but actually generally nice. Edit: I should point out that we were in Google NYC, as were the researchers. We had lunch with them some times. I remember the first name and face of the guy who submitted the slow code, but forget his family name and intentionally left his name out. New Yorker to New Yorker adds a lot of context. Google's corporate culture is generally very Californian, but this happened all within the New York office between people who generally got along pretty well and knew each other decently. In context, there was a heavy note of respect for someone's abilities and disappointment that they weren't performing at a top level. He wouldn't have been so harsh with someone who was new or was a weaker engineer, or someone who wasn't used to New York culture.
- a-dub 4y ago
  having spent time on both sides of the fence, i've noticed that there can be a rivalry of sorts between software engineers and ml/ds/researcher types. researcher types often get to work on problems that swe types find interesting, so some swes get grumbly. researcher types also tend to write pretty horrific code which adds salt to the wounds. but there also can be a sort of envy that emanates from the research side. many are fully aware of their shortcomings and are envious of the swes ability to get things done on computers cleanly. it often seems that there can be yearning to wear each other's hats from the two groups. if i were running a company i think i'd try to break down that wall as it would probably make a lot of people happier. of course, the right answer here isn't a meme... it's performance regression tests in the ci suite. and maybe a little training on why customizing a programming language with macros is bad.
  - KMag 4y ago
    > maybe a little training on why customizing a programming language with macros is bad Both the author and the reviewer had passed C++ style certification. They knew why it was bad. They just got a little lazy and wanted to write their code in a way that felt familiar to them, and figured it was harmless. I got a bit grumpy at having to drop what I was doing right away to fix their mistake due to their laziness.
    - a-dub 4y ago
      also, just to be clear. the macro only included open and close curlies? if so that's silly, as it is literally 2x the work to type. if they also included some sort of state that had to be managed, then it starts to verge towards reasonable.
      - KMag 4y ago
        I think that maybe the author felt like finding the end of a loop stood out much better that way, instead of trying to distinguish the ends of conditional blocks from the ends of loops. If you're used to poorly formatted code in an ML PhD program, it does make some sense. I've worked with a bit of academic Fortran code for my mechanical engineering degree and can sympathize. Also, D and O are shorter reaches on the keyboard than { and }. Yes, "OD" was definitely just "}". DO might have been ") {" to allow while (a < b DO ... OD
- jiggawatts 4y ago
  Conversely I would prefer to work in a place like that. Professionalism at scale isn’t achievable by tolerating idiotic behaviour and being nice to everyone no matter how dangerously stupid they are being. There is a point where someone has to put their foot down and demand things be done properly, otherwise the inevitable consequence is a giant mess leading to disaster. You might be used to small startup teams with responsible, experienced developers. Out there in larger industry you get people doing absolutely crazy things that break huge, expensive systems. There’s a difference between “oops I didn’t realise this library doesn’t scale the way I assumed it did” and “rewriting language symbols because I’m too stupid to use more than one syntax forever and ever.” The standard you walk past is the standard you accept. Are you saying you would walk past C code with DO…OD instead of {…}? Would you accept that standard just to be “nice” all the time?
  - runlevel1 4y ago
    There was a time when I would have agreed with that. What I've learned since then is that, with a healthy company culture, you can give frank feedback -- even about stupid mistakes -- without it being a rebuke. It's also important that you target the right problem. It's only human for smart people do stupid things sometimes. In the specific DO...OD example, I'd be more interested in how it got through a code review than the mistake itself. (Funny enough, early versions of the C source for Bash itself had macros like that.) Now, if someone exhibits a pattern of ignoring good, constructive feedback, that's a problem. The folks I've seen like that both gave terrible feedback and took feedback terribly. That's a behavioral problem, and you only get so many chances to correct that before it's time for them to find other employment.
  - jseban 4y ago
    > There is a point where someone has to put their foot down and demand things be done properly, otherwise the inevitable consequence is a giant mess leading to disaster. This is what management is for, too bad tech companies are too cool for that and prefer to live out lord of the flies.
    - alasdair_ 4y ago
Alex3917 4y ago
Re2 is also slower, so they might not be using it for high volume stuff. Also I’ve heard that Google automatically fails people who use regex in interviews, so their average engineers probably aren’t the best at it.
- KMag 4y ago
  > Also I’ve heard that Google automatically fails people who use regex in interviews, Hmm... I don't remember that, and I conducted over 100 interviews back when I was at Google. A blanket failure for using a regex sounds like it's missing some nuance. But, maybe that was before or after my time. I wouldn't be surprised if they start out with some interview questions that are easy to implement as regexes, but then gradually make the question harder and more general, where a pushdown automaton is necessary for a general correct solution, and fail people who either don't get a correct answer or end up implementing a pushdown automaton by dynamically generating larger and larger regexes.
  - Alex3917 4y ago
    I think it's more that you need to give the O(n) of your answer, which is generally very difficult to do with regex. And even if it's possible, it might not be an acceptable O(n). In general regexes finish instantly for normal sized inputs, but the actual O(n) might be quadratic or whatever.
vl 4y ago
But why it even happened? Typically you run Flume over docjoins in your project’s quota. If you screw up, all that should happen is that your Flume job is out of quota.
- KMag 4y ago
  This was in the Borg days, pre-Flume. As I remember, we had at least one Borg cluster to ourselves for indexing. Our quota was a cluster. We cared because indexing latency is important. Engineers get paged and woken up in the middle of the night when indexing latency gets high. Doubling CPU usage meant doubling indexing latency. The pre-Percolator indexing system ran roughly 1,000 threads per box on roughly 1,000 Warp18 boxes. Of course, most of those threads were blocked on I/O. (Warp18 was something like 16 cores per box... I think those were the RevE Opterons that had the memory fence bug that caused the glibc semaphore implementation to not actually synchronize operations.) I personally would have written things using more async and/or non-blocking I/O, but the main reasoning in Google at the time was that massively multithreaded blocking I/O is a simpler programming model and closer to what was being taught in school those days. Also, the indexing system's quota is huge. Someone made a mistake in their benchmark program that they thought got maximum utilization out of the Warp18 hardware. The indexing system actually got higher utilization than the hardware stress-test, resulting in cooling being under-provisioned in the Atlanta datacener (more than a decade ago, I'm sure indexing has moved now). There was a couple day stretch one hot Summer where we needed to stay on the phone with staff inside the Atlanta DC to keep track of the temperature inside the datacenter. When the temperatures started to get above something like 80 F, we needed to dial back on the number of workers in our Borg jobs. While testing the prototype for the Percolator indexing system, we were luckily sitting right next to an engineer who planned datacenters. We luckily overheard him saying he couldn't figure out why the power usage seemed to be swinging so wildly. It was literally the power usage of a decent sized town suddenly ramping up and down. We asked him the exact times power usage was ramping up and down, and figured out it was when Frank and Daniel were starting and stopping the Percolator prototype. My best guess is that the indexing system right before Percolator was a bit more energy efficient than Percolator, but maybe not. In any case, doubling CPU usage was a big deal. Real money, and in Atlanta, probably real carbon footprint. (The Dales was hydro, but I don't think much of Atlanta's power was renewable at that time.)
rad_gruchalski 4y ago
> Ironic, from the authors of RE2. They know the correct way to implement regexes. > Probably… Conclusions.
dllthomas 4y ago
> "DO" for "{" and "OD" for "}" so that they could write C++ a bit more like Bash. Bash (like Bourne shell before it) uses do/done. I think DO/OD was in an Algol (68?). I'm not sure where else? Bash does do the reversing for if/fi and case/esac, though.
- fanf2 4y ago
  Steve Bourne wanted to use `od` to match Algol 68, but there was already an `od` utility for printing octal dumps. The original bournegol macros for DO and OD were a bit different: #define DO ){ #define OD ;} https://www.tuhs.org/cgi-bin/utree.pl?file=V7/usr/src/cmd/sh/mac.h https://www.tuhs.org/cgi-bin/utree.pl?file=V7/usr/src/cmd/sh...

ikiris 4y ago

You just triggered probably 50 sres involved in this bug.