drothlis

This "not quite 5 minute guide to making an NTP server" is from 2014: https://ava.upuaut.net/?p=726

So GPS boards for Raspberry Pi were cheap off-the-shelf hardware by 2014, at least.

I don't know much about Python's C API, but this is the line in the OpenCV Python bindings that drops the GIL: https://github.com/opencv/opencv/blob/4.5.0/modules/python/s...

(see https://docs.python.org/3/c-api/init.html#releasing-the-gil-... in the Python C API manual).

That's only called from the ERRWRAP2 macro here: https://github.com/opencv/opencv/blob/4.5.0/modules/python/s...

That macro, in turn, is called from gen_template_func_body in gen2.py: https://github.com/opencv/opencv/blob/4.5.0/modules/python/s...

And that seems to be a code generator that is generating the bindings for all the OpenCV functions: https://github.com/opencv/opencv/blob/4.5.0/modules/python/s...

As to testing this, on Linux I'd run `atop` to see if your program is using all available CPUs.

I believe many (most?) opencv & numpy operations release the GIL.

Good point about OpenCV's in-place operations. Sometimes it's tricky/impossible to do that in numpy if you need to implement something that OpenCV doesn't provide. For example the C code that I linked in my previous comment, we wrote as an optimization of OpenCV's `matchTemplate` when the inputs meet a specific condition (that both input images are the same size). In C we do the multiplications as we iterate over the images and we maintain a rolling sum in a single variable. In numpy you can't really do this, you have to multiply the whole array and then sum the result.

For 720p images our C implementation[1] was 100x faster than our numpy implementation[2], and 10x faster than numba[3].

[1]: https://github.com/stb-tester/stb-tester/blob/v32/_stbt/sqdi...

[2]: https://github.com/stb-tester/stb-tester/pull/566/files#diff...

[3]: https://github.com/stb-tester/stb-tester/pull/566/files#diff...

For the curious, if you want to avoid numpy's memory overhead[1] here's how you'd do it in C with no dependencies: https://github.com/stb-tester/stb-tester/blob/v32/_stbt/sqdi...

This C code isn't doing exactly the same thing; here it's calculating a global similarity measure by calculating sum-of-squared-differences and comparing the end sum against the specified threshold, instead of comparing each pixel-wise diff against the threshold.

It is straightforward C code but it's vectorised by the compiler: https://godbolt.org/z/-3uO1z

Excluding the overhead of reading & decoding the PNGs, it takes 80ms for the same 8400x4725 images as my parent comment.

Benchmark:

  $ git clone git@github.com:stb-tester/stb-tester.git
  $ cd stb-tester
  $ make
  $ ipython
  >>> import _stbt.sqdiff, cv2, timeit
  >>> f1 = cv2.imread("water-4k.png")
  >>> f2 = cv2.imread("water-4k-2.png")
  >>> timeit.timeit(lambda: _stbt.sqdiff._sqdiff_c(f1, f2), number=1)
  0.081

[1] The Python code in my parent comment will allocate memory (the size of the entire image) for each intermediate calculation like the colourspace conversion, the absolute differences, etc.

I too was surprised that OP's imgdiff is "3X faster than the fastest in the world pixel-by-pixel image difference tool". I would have expected imagemagick etc to be faster.

Here's some Python code (using OpenCV & numpy) that is roughly equivalent to OP's imgdiff. It is single-threaded but it'll be vectorised and it's 3x faster on my 5-year-old 2-core laptop (even counting the Python overhead):

  import sys, cv2, numpy
  
  f1 = cv2.imread(sys.argv[1])
  f1 = cv2.cvtColor(f1, cv2.COLOR_BGR2GRAY)
  f2 = cv2.imread(sys.argv[2])
  f2 = cv2.cvtColor(f2, cv2.COLOR_BGR2GRAY)
  threshold = 0.1
  
  absdiff = cv2.absdiff(f1, f2)
  _, thresholded = cv2.threshold(
      absdiff, int(threshold * 255),
      255, cv2.THRESH_BINARY)
  
  cv2.imwrite("output.png", thresholded)
  print("Different pixels: %s" % numpy.count_nonzero(thresholded))

Benchmark:

  $ /usr/bin/time python test.py water-4k.png water-4k-2.png
  Different pixels: 89153
  1.39user 0.34system 0:01.33elapsed 129%CPU

  $ /usr/bin/time ./imgdiff water-4k.png water-4k-2.png output.png
  Failure! Images are different.
  Different pixels: 89142
  Command exited with non-zero status 1
  8.85user 0.10system 0:04.02elapsed 222%CPU

(Edit: The Python code is a simplified version extracted from https://github.com/stb-tester/stb-tester -- we use it for regression testing of GUI screenshots.)

> Ninja looks like it tracks dependencies roughly automatically, whereas dependencies are manual in Make

Ninja has built-in support for the ".d" files generated by gcc's "-M" family of flags, but you still have to make your gcc command-line actually pass the right flags, and you have to tell Ninja the name of the ".d" file. See https://lwn.net/Articles/706404/

Another neat feature of Ninja is that it's much better at "pruning" downstream targets if you rebuilt something (because of an out-of-date timestamp) but then it turned out to be bit-for-bit identical as it was before. In this case, downstream targets that depend on this intermediate target don't need to be rebuilt.

> If commit messages refer to other commits by ID (e.g. "this reverts commit 01234567890abcdef", "In commit 0013deadbeef9a..."), those commit messages should be rewritten to refer to the new commit IDs

Finally, a tool that does this! I wish git rebase could do it.

It’s sometimes more than one click, but “git blame” (built into the IDE) serves that purpose for me.

We too found that the FT232R is unusable in bitbang mode. After much to-and-froing, FTDI support eventually acknowledged that even their later hardware revision "C" is still buggy, despite what the errata sheet implied.

We switched to the FT230X, which works great.

Our detailed investigation: https://stb-tester.com/blog/2016/05/26/ir-post-mortem

Another thought related to characterisation testing, this time from Jeremias Roessler's talk at QAFest Ukraine 2017 (https://www.youtube.com/watch?v=f4PT_u8hjhU): Traditional automated tests (with asserts) are "blacklisting" the changes that aren't allowed, whereas a characterisation test will catch any change in behaviour, and instead you have to "whitelist" the changes that are allowed (by providing regexes or some kind of pattern to match the dynamic output that is allowed to change).

This technique is also known as characterisation testing, golden-master testing, snapshot testing, and probably other names too. I recommend looking into https://approvaltests.com/ (already mentioned by another commenter).

I use characterisation testing all the time, in a perhaps unusual application: Checking the behaviour of "Page Objects" (classes used to model the application-under-test in GUI-level automated testing) when the application-under-test has changed. That's right: Automated [characterisation] tests for my automated [GUI] tests! It makes GUI testing oh so much easier to maintain. I wrote it up here: https://david.rothlis.net/pageobjects/characterisation-tests

The OP is 100% right that ninja's biggest architectural insight is the "assembler" metaphor. I came to this same conclusion in https://lwn.net/Articles/706404/

Sad to hear the overall experience has been so negative for him. Ninja has certainly had a large impact! I can relate to the open-source burnout, even though I've experienced only a tiny tiny fraction of it compared to the success of Ninja.

Re. speed, I wonder how much of Ninja's speed over make is thanks to Ninja's "deps log" binary format. In my (fabricated) benchmarks, Make spent 98% of its time processing the compiler-generated ".d" files that are used to track dependencies on header files: https://david.rothlis.net/ninja-benchmark/

Thanks for the link -- it was really interesting.

For other HN readers: The parent works at RedHat (on distro-wide build/packaging? He talks about building Fedora packages) and there are some useful ideas in there.

My own notes & thoughts having just watched the video:

## "Tactic" allows a target that aren't files ##

- For example a target #url("http://xyz/abc"): to "build" it, scp the dependency to the server.

[Edit: I had to replace * with # in "* url" above because of HN formatting.]

How does it check if the file at the url is out of date? Would be terribly slow if it had to fetch it each time.

- For example #koji-built("package-name"): used to rebuild fedora packages in the right dependency order, if needed, using a remote build service.

I suppose you can implement this in make/ninja by creating dummy marker files like ".url.http_xyz_abc.built" as your target, but it's a hassle.

## Multiple parameters ##

- make rules support a single parameter, i.e. the "%" in "%.o: %.c"

- his tool supports arbitrary parameters:

    goal compile (name, debug) =
    "%name.%debug.o" : "%name.c" {
        if [ % debug = d ]; then f=-DDEBUG=1; fi
        ...
    }

I've been using a python script to generate ninja files, so I achieve the same by using normal Python functions with arguments; plus ninja's built-in support for rebuilding the target if the recipe has changed.

## Shell problems in make ##

1. filenames with spaces - his tool supports it by forcing filenames to be quoted. "some_name" is syntactic sugar for #file("some_name") (see "tactics" above).

2. make (by default) uses a separate shell per recipe line.

3. dollar interpreted by make so have to use $$var - his tool solves this by using % as the escape character.

I think ninja solves the first 2 automatically. I solve the 3rd one by doing the escaping ($ -> $$) in the Python script that generates my ninja files.

## Named goals ##

If you have a "goal" (rule) called "compile" then you can use the goal invocation as a dependency. For example these 2 are equivalent:

    goal link = "prog": "foo.o"

and

    goal link = "prog": compile("foo")

THIS IS A BIG DEAL. It means you don't have to come up with artificial target names (filenames) for intermediate build steps. In my own Python+ninja builds, each Python function returns the target, which you can use as input to other functions, and this has turned out to be super useful. For example (Python code):

    def build_package(name, build_root_yaml):
        build_root = build_container(name, build_root_yaml)
        src = tarball_to_ostree(git_archive(repo, sha, prefix="src/"))
        return run_command("make -C /src install DESTDIR=/dest",
                           ostree_combine([build_root, src]),
                           chroot=True,
                           out_subdir="/dest")

This snippet creates a filesystem image (build_root), creates a source tarball using "git archive", unpacks that tarball into the build root, then and chroots into the build root to run a build command, capturing the tree created in "/dest" as a new build artifact. The return value is target representing this build artifact -- you can pass it into other functions. It's still a filename, but it can be generated automatically, for example as a hash of the inputs.

Note that running this python code doesn't actually do any of this building; it just writes out a ninja file that will do it. The return value (from the python function) is the target name. Each of "build_container", "tarball_to_ostree", "git_archive", "run_command", and "ostree_combine" are Python functions that behave in a similar way (writing out ninja rules and returning the target).

(I need to do a proper write-up of how we use Python+ninja+ostree in our build system. I hope the above made some sense at least.)

## Computer sciency things ##

He talks about how his named goals are like functions, that can be called by name or by pattern matching. I need to think about it a bit more to really understand the implications.

---

Thanks again for the talk. I hope this doesn't come across as "but you can already do this in ninja!". I just find it interesting to have new ways & words to think about various build system features/capatibilies, and to compare how different build tools tackle it. (In this vein I recommend the "build systems a la carte" talk/paper mentioned in the OP.)

On iOS 13: Settings > Passwords & Accounts > Select each account > Disable the "Mail" slider.

Cut means "if you matched this far, don't consider other options even if the current option fails to parse".

With this grammar:

    expr: expr '+' term | term

And this input:

    5 +

It will first consider the first alternative (expr '+' term) but will fail to match that branch because it's missing the "term" after the "+". That's fine because there's another alternative to try (term). That alternative doesn't match either, and you'll get the error message from the last alternative that it tried (probably something like "unexpected +").

But with this grammar:

    expr: expr '+' <cut> term | term

Then with the same input ("5 +") it will consider the first alternative, fail to match, and then fail immediately with the error message from that first alternative (something like "missing term after +").

It looks like libxo does the output in structured format, but what about input? (For chaining commands together with pipes). Did the FreeBsd porting work[1] implement the input side with libxo, independently of libxo, or not at all?

(Not to diminish libxo --it looks pretty cool, and I didn't know about it before-- just curious.)

[1]: https://wiki.freebsd.org/LibXo

Or git lfs, which is even supported by / integrated into github and other git hosting services.

You might also like http://david.rothlis.net/c/compilation_model/ -- a tutorial I wrote that goes into some detail on what the preprocessor, compiler, assembler & linker do.

11-50 employees according to https://www.crunchbase.com/organization/hybridcluster#/entit...

I wonder if most of those include files were the files auto-generated by the C pre-processor to track header file dependencies. In a toy benchmark[1] GNU Make spent 98% of its time processing those include files (for a no-op build). Ninja has a special optimisation for these files, where it reads them the first time they're created, inserts the dependency information into a binary database, then deletes them so it doesn't have to parse them in future invocations. AFAICT this accounts for most of Ninja's speed improvement over Make.

[1]: http://david.rothlis.net/ninja-benchmark/

I like to highlight just the places where you are defining new variables/functions/types so that the definition is easy to spot. What is the point of highlighting keywords? I suspect that highlighting engines do it simply because it's easy to do, not because it's useful.

It looks like this: http://david.rothlis.net/code_presentation/distracting_synta...

Yes, the Coursera ML course is equally hand-holdey. (I'd still recommend it anyway.)

The article links to a paper[1] that talks about online learning:

> The perceptrons are trained by an algorithm that increments a weight when the branch outcome agrees with the weight’s correlation and decrements the weight otherwise.

A "perceptron" seems to be a single linear function, akin to a single neuron in a neural network. So complex learning algorithms like back-propagation don't apply here.

The complete process, from the paper, is:

> 1. The branch address is hashed to produce an index "i" into the table of perceptrons.

> 2. The "i"th perceptron is loaded from the table into a vector register "P" of weights.

> 3. The value of "y" is computed as the dot product of "P" and the global history register. [This is a shift register containing values of -1 or 1 for the last N branches seen. -1 means not taken, and 1 means taken.]

> 4. The branch is predicted "not taken" when "y" is negative, or "taken" otherwise.

> 5. Once the actual outcome of the branch becomes known, the training algorithm uses this outcome and the value of "y" to update the weights in "P".

> 6. "P" is written back to the "i"th entry in the table.

The article says that AMD's microarchitecture uses a hashed perceptron system in its branch prediction. So, from the above, it seems that "hashed" means that you hash the branch address to pick which perceptron (model) to use, and "perceptron" is just a dot product. (Actually the wikipedia article[2] suggests that the name "perceptron" refers to the training algorithm, i.e. how you update the weights.)

[1]: Daniel A. Jiménez and Calvin Lin. 2002. Neural Methods for Dynamic Branch Prediction. https://www.cs.utexas.edu/~lin/papers/tocs02.pdf

[2]: https://en.wikipedia.org/wiki/Perceptron

I second the UVC driver recommendation, or anything with drivers upstream (that is, in the Linux kernel itself). If this is for your day job spending £250 is well worth it for one of the better quality brands, otherwise you'll be spending far more than that debugging reliability issues.

Depending on your project, it might be worthwhile using GStreamer instead of tying yourself to a specific driver like libuvc. There's a lot you can do with just GStreamer's command-line tools -- for some examples see the first 5 minutes of my talk[1] -- and if you need more you can drop down into C or Python, though admittedly the learning curve is fairly high.

[1]: http://www.youtube.com/watch?v=Fdn2LxxM7wA&list=SPSIUOFhnxEi...

Intel GPUs + VAAPI (https://01.org/linuxgraphics/community/vaapi) can easily do H.264 encoding in real time.

P.S. See also https://trac.ffmpeg.org/wiki/HWAccelIntro

Blackmagic's Linux drivers are gratis, but not libre. And of course they aren't upstream. This means that they are only guaranteed to work if you use exactly the same kernel that Blackmagic supports -- we've had all sorts of problems with them: the cards lock up (requiring a reboot before they will work again); the whole system locks up; the drivers were randomly overwriting other processes' memory (!); etc.

However our reliability requirements may be different than yours & the OP's, as we (at http://stb-tester.com ) use video capture for automated UI testing so we need rock-solid reliability.

I concur with the other commenter that devices with an upstream driver --such as the UVC driver-- are the way to go.

Presumably by "this site" mikek meant the site hosting the article.

See also the article linked earlier in the comments: https://blog.phusion.nl/2015/01/20/docker-and-the-pid-1-zomb...

Interesting (I'm not a kernel developer). What's the workflow at the subsystem level -- does the maintainer do a `git fetch` followed by `git rebase`? Or is the rebasing done via email patches and `git am`?

> I think it is quite telling that the Linux kernel developers themselves prefer a simple, linear history in the end

What do you mean? This is what the current git history of the linux kernel looks like:

    *   12b9fa6 Merge branch 'for-linus' of git://git.kernel.org/pu
    |\  
    | * 5129fa4 do_last(): ELOOP failure exit should be done after 
    | * a7f7754 should_follow_link(): validate ->d_seq after having
    | * d456564 namei: ->d_inode of a pinned dentry is stable only 
    | * c80567c do_last(): don't let a bogus return value from ->op
    | * 0fcbf99 fs: return -EOPNOTSUPP if clone is not supported
    | * b6853f7 hpfs: don't truncate the file when delete fails
    * |   340b3a5 Merge tag 'armsoc-fixes' of git://git.kernel.org/
    |\ \  
    | * \   d877a21 Merge tag 'renesas-soc-fixes-for-v4.5' of git:/
    | |\ \  
    | | * | 901c5ff ARM: shmobile: Remove shmobile_boot_arg
    | | * | 4e960f5 ARM: shmobile: Move shmobile_smp_{mpidr, fn, ar
    | | * | b1568d8 ARM: shmobile: r8a7779: Remove remainings of re
    | | * | d2613f5 ARM: shmobile: Move shmobile_scu_base from .tex
    | * | | 7931845 MAINTAINERS: Extend info, add wiki and ml for m
    | * | |   9fa6c2b Merge tag 'omap-for-v4.5/fixes-rc5' of git://
    | |\ \ \  
    | | * | | 3f315c5 ARM: OMAP2+: Fix onenand initialization to av
    | | * | | e327b3f Revert "regulator: tps65217: remove tps65217.
    | * | | | a9e5547 MAINTAINERS: alpine: add a new maintainer and
    | * | | | 5e45a25 ARM: at91/dt: fix typo in sama5d2 pinmux desc
    | * | | |   b223c9f Merge tag 'imx-fixes-4.5' of git://git.kern
    | |\ \ \ \  
    | | * | | | f5d0ca2 ARM: dts: imx6: remove bogus interrupt-pare
    | | | |/ /  
    | | |/| |   
    | * | | |   e3acd74 Merge tag 'omap-for-v4.5/fixes-rc3-v2' of g
    | |\ \ \ \  
    | | | |/ /  
    | | |/| |   
    | | * | | cf26f11 ARM: OMAP2+: Fix omap_device for module reloa
    | | * | | 08c78e9 ARM: OMAP2+: Improve omap_device error for dr
    | | * | | bf26927 ARM: DTS: am57xx-beagle-x15: Select SYS_CLK2 
    | | * | | a5b8751 ARM: dts: am335x/am57xx: replace gpio-key,wak
    | | * | | 5f35dc4 ARM: OMAP2+: Set system_rev from ATAGS for n9
    | * | | |   74a46ec Merge tag 'mvebu-fixes-4.5-2' of git://git.
    | |\ \ \ \  
    | | * | | | 44361a2 ARM: dts: orion5x: fix the missing mtd flas
    | | * | | | 9d021c9 ARM: dts: kirkwood: use unique machine name
    * | | | | |   691429e Merge branch 'akpm' (patches from Andrew)
    |\ \ \ \ \ \  
    | * | | | | | 7f6d5b5 dax: move writeback calls into the filesy

Merge commits galore.