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

Testing is better than data structures and algorithms

nedbatchelder.com

Post reply on HN
Print view View original

71–80 of 178 posts

Re: Testing is better than data structures and algorithms

#71

Post by wubrr »

sarchertech wrote: post #68
wubrr wrote: post #62

Earlier quoted context omitted.

> Testing concurrency is extremely hard Writing a non-trivial concurrent system based on your understanding of the 'algorithm' , without relying on testing is much harder. > I truly wonder if there is real world tests around this Of course there are. There are many tools, methods, and test suites out there for concurrency testing, for almost any major language out there. Of course, understanding your algorithm, and t…

I’ve never worked somewhere (in 20 years from big tech companies to small startups) that was generally and reliably testing for concurrency bugs. And I’ve seen dozens of bugs caused by people assuming that transactions (with the default isolation level) protect against race conditions.

Every place I worked at, that had any kind of reliable, high-throughput concurrent system had an extensive suite of concurrent tests.

https://github.com/postgres/postgres/tree/master/src/test/is...

https://muratbuffalo.blogspot.com/2023/08/distributed-transa...

https://learn.microsoft.com/en-us/archive/msdn-magazine/2008...

https://go.dev/blog/synctest

https://learntla.com/core/concurrency.html

Re: Testing is better than data structures and algorithms

#72

Post by wubrr »

JackSlateur wrote: post #70
wubrr wrote: post #62

Earlier quoted context omitted.

> Testing concurrency is extremely hard Writing a non-trivial concurrent system based on your understanding of the 'algorithm' , without relying on testing is much harder. > I truly wonder if there is real world tests around this Of course there are. There are many tools, methods, and test suites out there for concurrency testing, for almost any major language out there. Of course, understanding your algorithm, and t…

Running 1000x queries in a loop is called luck.

No, it's called testing many concurrent operations.

Implementing a complex concurrent algorithm based on your understanding of it, without proper testing is called luck, and often called delusion.

Re: Testing is better than data structures and algorithms

#73

Post by fuzztester »

wjrb wrote: post #2

Are there any resources out there that anyone can recommend for learning testing in the way the author describes? In-the-trenches experience (especially "good" or "doing it right" experience) can be hard to come by; and why not stand on the shoulders of giants when learning it the first time?

The Art of Software Testing. New York: Wiley, 1979

The Art of Software Testing, Second Edition. with Tom Badgett and Todd M. Thomas, New York: Wiley, 2004.

It is by Glenford Myers (and others).

https://en.m.wikipedia.org/wiki/Glenford_Myers

From the top of that page:

[ Glenford Myers (born December 12, 1946) is an American computer scientist, entrepreneur, and author. He founded two successful high-tech companies (RadiSys and IP Fabrics), authored eight textbooks in the computer sciences, and made important contributions in microprocessor architecture. He holds a number of patents, including the original patent on "register scoreboarding" in microprocessor chips.[1] He has a BS in electrical engineering from Clarkson University, an MS in computer science from Syracuse University, and a PhD in computer science from the Polytechnic Institute of New York University. ]

I got to read it early in my career, and applied it some, in commercial software projects I was a part of, or led, when I could.

Very good book, IMO.

There is a nice small testing-related question at the start of the book that many people don't answer well or fully.

Re: Testing is better than data structures and algorithms

#74

Post by sarchertech »

wubrr wrote: post #71
sarchertech wrote: post #68

Earlier quoted context omitted.

I’ve never worked somewhere (in 20 years from big tech companies to small startups) that was generally and reliably testing for concurrency bugs. And I’ve seen dozens of bugs caused by people assuming that transactions (with the default isolation level) protect against race conditions.

Every place I worked at, that had any kind of reliable, high-throughput concurrent system had an extensive suite of concurrent tests. https://github.com/postgres/postgres/tree/master/src/test/is... https://muratbuffalo.blogspot.com/2023/08/distributed-transa... https://learn.microsoft.com/en-us/archive/msdn-magazine/2008... https://go.dev/blog/synctest https://learntla.com/core/concurrency.html

> Every place I worked at, that had any kind of reliable, high-throughput concurrent system

Pretty much anyone with high throughput is running a high throughput concurrent system, and very few companies have an extensive suite of concurrency tests unless you just mean load tests (that aren’t setup to catch race conditions).

The “reliable” part of that statement might be doing a lot of heavy lifting depending on what exactly you mean by that.

Re: Testing is better than data structures and algorithms

#75

Post by JackSlateur »

wubrr wrote: post #72
JackSlateur wrote: post #70

Earlier quoted context omitted.

Running 1000x queries in a loop is called luck.

No, it's called testing many concurrent operations. Implementing a complex concurrent algorithm based on your understanding of it, without proper testing is called luck, and often called delusion.

What algorithm ? The whole idea is that algorithms are useless, and you should just write a bunch of tests and go with it

Yes, if I write stuff with locks, I shall ensure that my code acquires and releases locks correctly

This is completely off-topic with the original post;

Also, you cannot prove something by tests; Just because you found 100000 cases where your code works does not mean there is not a case where is does not (just as you cannot prove that unicorn does not exist) :)

Re: Testing is better than data structures and algorithms

#76

Post by pncnmnp »

IvyMike wrote: post #66

Always gonna have to side with Peter Norvig on this one: https://pindancing.blogspot.com/2009/09/sudoku-in-coders-at-... > They said, “Look at the contrast—here’s Norvig’s Sudoku thing and then there’s this other guy, whose name I’ve forgotten, one of these test-driven design gurus. He starts off and he says, “Well, I’m going to do Sudoku and I’m going to have this class and first thing I’m going to do is write a bun…

I love what Norvig said. I can relate to it. As far as data structures are concerned, I think it's worth playing smart with your tests - focus on the "invariants" and ensure their integrity.

A classic example of invariant I can think of is the min-heap - node N is less than or equal to the value of its children - the heap property.

Five years from now, you might forget the operations and the nuanced design principles, but the invariants might stay well in your memory.

Re: Testing is better than data structures and algorithms

#77

Post by matheusmoreira »

fastaguy88 wrote: post #29

It really depends. Working on genome analysis, I once encountered/interrupted (by rebooting after a software update) a student who had been running an analysis for more than a week, because they had not pre-sorted the data. With pre-sorted data, it took a few minutes. Not everyone works on web sites using well-optimized libraries; some people need to know about N and Nlog(N) vs N^2.

> some people need to know about N and Nlog(N) vs N^2.

Every programmer should know enough to at least avoid accidentally making things quadratic.

https://news.ycombinator.com/item?id=26296339

Re: Testing is better than data structures and algorithms

#78

Post by teraflop »

wubrr wrote: post #72
JackSlateur wrote: post #70

Earlier quoted context omitted.

Running 1000x queries in a loop is called luck.

No, it's called testing many concurrent operations. Implementing a complex concurrent algorithm based on your understanding of it, without proper testing is called luck, and often called delusion.

You can't easily, automatically test concurrent code for correctness without testing all possible interleavings of instructions, and that state space is usually galactically huge.

It is very easy to write multithreaded code that is incorrect (buggy), but where the window of time for the incorrectness to manifest is only a few CPU instructions at a time, sprinkled occasionally throughout the flow of execution.

Such a bug is unlikely to be found by test cases in a short period of time, even if you have 1000 concurrent threads running. And yet it'll show up in production eventually if you keep running the code long enough. And of course, when it does show up, you won't be able to reproduce it.

That is, I think, what the parent commenter means by "luck".

This is similar to the problem you'll run into when testing code that explicitly uses randomness. If you have a program that calls rand(), and it works perfectly almost all the time but fails when rand() returns the specific number 12345678, and you don't know ahead of time to test that value, then your automated test suite is unlikely to ever catch the problem. And testing all possible return values of rand() is usually impractical.

Re: Testing is better than data structures and algorithms

#79

Post by sarchertech »

JackSlateur wrote: post #75
wubrr wrote: post #72

Earlier quoted context omitted.

No, it's called testing many concurrent operations. Implementing a complex concurrent algorithm based on your understanding of it, without proper testing is called luck, and often called delusion.

What algorithm ? The whole idea is that algorithms are useless, and you should just write a bunch of tests and go with it Yes, if I write stuff with locks, I shall ensure that my code acquires and releases locks correctly This is completely off-topic with the original post; Also, you cannot prove something by tests; Just because you found 100000 cases where your code works does not mean there is not a case where is d…

> Also, you cannot prove something by tests; Just because you found 100000 cases where your code works does not mean there is not a case where is does not (just as you cannot prove that unicorn does not exist) :)

That’s exactly it. For any non trivial program, there exists an infinite number of ways your program can be wrong and still pass all your tests.

Unless you can literally test every possible input and every bit of state this holds true.

Re: Testing is better than data structures and algorithms

#80

Post by philwelch »

jerf wrote: post #23

This is one of the things I'd tune in the current curriculum. When I went to college in the late 1990s, we were right on the verge of a major transition to DSAs being something every programmer would implement themselves to something that you just pick up out of your libraries. So it makes sense that we would have some pretty heavy-duty labs on implementing very basic data structures. That said, I escaped into the dy…

I don’t think the primary value in learning data structures and algorithms is the ability to implement them yourself. It’s more of a way to get repetitions in on basic programming skills while learning about the tools that are available to you. Later in a CS curriculum you might learn how to write an operating system or a compiler, not because you’re necessarily going to ever actually do it again but because it’s a way of learning how those systems work as well as getting repetitions building larger projects.
Post reply on HN