Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Don’t underestimate grep-based code scanning

littlemaninmyhead.wordpress.com

Post reply on HN
Print view View original

101–110 of 122 posts

Re: Don’t underestimate grep-based code scanning

#101

Post by burntsushi »

jandrese wrote: post #93
jlebar wrote: post #91

Earlier quoted context omitted.

String search algorithms can cleverly skip forward when they don't find a match. They can skip forward more for longer "needle" strings. That said grep is pretty fast period, so probably doesn't make a huge difference in practice, especially if you're IO-bound, which is common.

The caveat being if you're Unicode aware then many of the old skipahead strategies don't work as well and have to be rolled back or disabled.

That's not true. They work just fine. Typically, substring search algorithms are implemented at the encoding level, e.g., on UTF-8 directly. If you just treat that as an alphabet of size 256, then algorithms like Boyer-Moore work out of the box.

But the skip-ahead stuff isn't the most important thing nowadays. The key is staying in the fast vectorized skip loop as long as possible.

Re: Don’t underestimate grep-based code scanning

#102

Post by jandrese »

burntsushi wrote: post #101
jandrese wrote: post #93

Earlier quoted context omitted.

The caveat being if you're Unicode aware then many of the old skipahead strategies don't work as well and have to be rolled back or disabled.

That's not true. They work just fine. Typically, substring search algorithms are implemented at the encoding level, e.g., on UTF-8 directly. If you just treat that as an alphabet of size 256, then algorithms like Boyer-Moore work out of the box. But the skip-ahead stuff isn't the most important thing nowadays. The key is staying in the fast vectorized skip loop as long as possible.

I noticed severe slowdowns when passing in the /u flag on my regexes, even with big fixed ASCII strings in the middle of the patterns. They were taking 10 times as long to complete.

Re: Don’t underestimate grep-based code scanning

#103

Post by deathanatos »

unilynx wrote: post #84
alxmdev wrote: post #82

Hold on, strncat and strncpy are considered dangerous too, now? Not just the older versions without the size_t num argument?

They don't \0-terminate the target on overflow, so you still need to test for that condition. So most people will have a wrapper around those to ensure the \0 is there.

strncpy() acts as you describe, but strncat() will terminate; from its man page[1],

> the resulting string in dest is always null-terminated.

[1]: https://linux.die.net/man/3/strncat

Re: Don’t underestimate grep-based code scanning

#104

Post by deathanatos »

alxmdev wrote: post #82

Hold on, strncat and strncpy are considered dangerous too, now? Not just the older versions without the size_t num argument?

In addition to what unilynx mentions about strncpy(), the size arguments are also, effectively, the remaining space in the destination buffer, not the entire space in the destination buffer.

So, you have to figure that out. It isn't hard (hell, it's trivial) but I think if you're either going to be aware of the pitfalls — and then these functions are mostly not going to help you — or you're not, in which case you're just as likely to pass the wrong value for the size (dest's size/src's size) and overflow the buffer anyways.

Honestly, if I had to do more than a trivial amount of string manipulation in C, I'd be wrapping that in a mini library to manage some sort of stronger string type or finding such a library (glib? ICU?) very quickly, depending on needs. std::string was one of the things in C++ that made me question why anyone was still using C, given how much less error-prone it is, comparatively. (std::string is not without problems / only as compared to char * in C.)

Re: Don’t underestimate grep-based code scanning

#105

Post by Annatar »

adwn wrote: post #27
Annatar wrote: post #22

Earlier quoted context omitted.

Real fgrep does not implement -r because that would be implementing tools within tools, which is against the UNIX®️ philosophy. Try /usr/bin/find . -depth -type f -print | /usr/bin/xargs -i /usr/bin/fgrep string '{}' and run it several times so that the filesystem cache is primed.

> Real fgrep does not implement -r That's BS. The fgrep on my system – GNU grep 3.1 – provides recursive search (-r). What now, are you claiming that's not "real fgrep"? [1] > that would be implementing tools within tools, which is against the UNIX®️ philosophy Even more BS. Or are you telling me that "rm -r" is also against the "UNIX philosophy"? > /usr/bin/find . -depth -type f -print | /usr/bin/xargs -i /usr/bin/f…

"What now, are you claiming that's not "real fgrep"?

GNU stands for GNU is not UNIX®️.

Re: Don’t underestimate grep-based code scanning

#106

Post by [deleted] »

robohoe wrote: post #36
adwn wrote: post #27

Earlier quoted context omitted.

> Real fgrep does not implement -r That's BS. The fgrep on my system – GNU grep 3.1 – provides recursive search (-r). What now, are you claiming that's not "real fgrep"? [1] > that would be implementing tools within tools, which is against the UNIX®️ philosophy Even more BS. Or are you telling me that "rm -r" is also against the "UNIX philosophy"? > /usr/bin/find . -depth -type f -print | /usr/bin/xargs -i /usr/bin/f…

This is why Unix is great. It gives you enough tools to shoot yourself in the foot.

[deleted]

Re: Don’t underestimate grep-based code scanning

#107

Post by Annatar »

pjc50 wrote: post #29
Annatar wrote: post #22

Earlier quoted context omitted.

Real fgrep does not implement -r because that would be implementing tools within tools, which is against the UNIX®️ philosophy. Try /usr/bin/find . -depth -type f -print | /usr/bin/xargs -i /usr/bin/fgrep string '{}' and run it several times so that the filesystem cache is primed.

.. which falls over as soon as you have a file with a space in the name. Edit: this highlights the big weakness in the "UNIX philosophy", in which the only record delimiter that's conventionally recognized in pipelines is the newline but the shell recognizes characters as filename delimiters that are also allowed in filenames . Causing a cascade of delimiter bugs. Sometimes you really do need a bit more structure to…

All you have to do is replace the single with double quotation marks and my commands will handle spaces just fine.

Re: Don’t underestimate grep-based code scanning

#108

Post by Annatar »

eequah9L wrote: post #56
pjc50 wrote: post #29

Earlier quoted context omitted.

.. which falls over as soon as you have a file with a space in the name. Edit: this highlights the big weakness in the "UNIX philosophy", in which the only record delimiter that's conventionally recognized in pipelines is the newline but the shell recognizes characters as filename delimiters that are also allowed in filenames . Causing a cascade of delimiter bugs. Sometimes you really do need a bit more structure to…

> .. which falls over as soon as you have a file with a space in the name. Yeah, spaces are nasty. find has -print0 and xargs has -0 to handle this gracefully, but one needs to know to use it.

-print0 is a GNUism and isn't portable. As stated previously, replacing '{}' with "{}" will handle spaces and most metacharacters just fine.

Re: Don’t underestimate grep-based code scanning

#109

Post by burntsushi »

jandrese wrote: post #102
burntsushi wrote: post #101

Earlier quoted context omitted.

That's not true. They work just fine. Typically, substring search algorithms are implemented at the encoding level, e.g., on UTF-8 directly. If you just treat that as an alphabet of size 256, then algorithms like Boyer-Moore work out of the box. But the skip-ahead stuff isn't the most important thing nowadays. The key is staying in the fast vectorized skip loop as long as possible.

I noticed severe slowdowns when passing in the /u flag on my regexes, even with big fixed ASCII strings in the middle of the patterns. They were taking 10 times as long to complete.

That doesn't imply that things like Boyer-Moore suddenly stop being effective. Without more details (which regex engine? what regex? what corpus? which programming language?) it's impossible to state the cause, but it could be as simple as the regex engine not being smart enough to use a literal searcher in that case.

Re: Don’t underestimate grep-based code scanning

#110

Post by Annatar »

sctb wrote: post #61
Annatar wrote: post #23

Earlier quoted context omitted.

You obviously haven't tried it on either of those. They are "second tier", which means one is completely on one's own. What in your opinion would have to be the size of the source code to warrant jumping through the hoops to get this software running, as opposed to a combination of find + xargs + egrep,fgrep,awk?

Could you please review the guidelines and post less rudely and antagonistically? https://news.ycombinator.com/newsguidelines.html

When they post these misguided reinventions of the wheel which on top of that require gargantuan effort to get working for something as trivial as a find + grep, they antagonize me; and then they argue about GNU tools having never seen or worked on a real UNIX, it's blind leading the blind. Infuriating.
Post reply on HN