HNHacker News
TopNewBestAskShowJobs

profquail

6,978 karma · joined June 24, 2009

C#/F#/C++/Python developer. Building trading systems and strategies at Susquehanna: https://sig.com/Careers/

Twitter: @jkpappas

https://github.com/jack-pappas

https://fsharp.org

submissionscomments
profquail··on More challenging projects every programmer should try
The optimizations get you the following:

* Normalization: this is where "smart constructors" come in handy; having a normal form for the terms allows the caching to work better. This also impacts the compactness of the generated DFA. * Hash-consing: this turns structural equality (in this case) to a simple pointer equality; applied recursively, this makes it much faster to compare two terms for equality, and overall speeds up the DFA generation by a non-trivial amount (I forget the exact numbers, but it was significant). * Dense set implementation: The AVL tree-based data structure in the facio/Reggie code is an implementation of the Discrete Interval Encoding Tree (DIET) data structure from "Diets for fat sets" and "More on Balanced Diets" papers.

Note the optimizations I've mentioned here impact the performance of generating the DFA. Once you have the DFA, it'll run at the same speed as one generated in any other way. Part of the motiviation for my writing this library was to learn about regex/DFAs/grammars, but also to try to improve on the performance of fslex/fsyacc at the time. Using this library, the FSharpLex tool can generate the DFA for the full F# language grammar in well under 1 sec; the code generation takes a bit longer, largely due to having to convert the DFA into a different form for backwards-compatibility with fslex.

Overall, I feel like the derivatives technique is generally better and simpler, and I'm not aware of any real downsides. The only one that comes to mind is if you're wanting to implement things like backreferences and capture groups -- those obviously make the implementation (of the DFA) more complicated, and there's a lot less literature on it (last I saw, maybe only one or two papers on implementing those features on top of a derivatives-based regex engine).

profquail··on More challenging projects every programmer should try
I wrote an implementation of this several years back. If you’re interested in the code: https://github.com/jack-pappas/facio/tree/master/Reggie

The derivatives approach makes Unicode support easier since its able to keep the symbols sets for each transition edge (in the DFA) more compact by virtue of supporting negation. If you add in aggressive term-normalization, hash-consing, and an efficient dense-set implementation (all of which I’ve done in my implementation), the derivatives approach can be extremely fast, even when generating the DFA for something like the lexer of a full programming language (in my case, F#).

profquail··on How io_uring and eBPF Will Revolutionize Programming in Linux
The glommio library from DataDog was specifically built around io_uring: https://www.datadoghq.com/blog/engineering/introducing-glomm...
profquail··on It's Talos all the way down
Thanks for the link! This is really useful for developing/testing out code optimizations for POWER-based systems (e.g. for low-level bits like hashing functions, crypto, and vector math).
profquail··on Blosc – A high performance compressor optimized for binary data
Not generally, no. blosc is geared towards “rectangular” data — that is, a C-style array of int, double, or some struct type.
profquail··on MsQuic – QUIC Implementation from Microsoft
Have you considered implementing any parts of this in F* (so they can be verified) and extracting back to C, as is being done for TLS?

https://project-everest.github.io/

profquail··on PostgreSQL is the worlds’ best database
HeidiSQL: https://www.heidisql.com/

Bonus — it also works for MySQL/MariaDB, MS SQL, and sqlite.

profquail··on Distinct on: a confusing, unique and useful feature in Postgres
Isn’t this what the LAST_VALUE window function does? If so, that’s a standardized SQL syntax which is supported in both postgresql and recent versions of MySQL.

https://www.postgresqltutorial.com/postgresql-last_value-fun...

profquail··on He Has 17,700 Bottles of Hand Sanitizer and Nowhere to Sell Them
Slightly offtopic, but should you need sanitizer and your local stores are out of stock — perhaps due to people like the subjects of this article — you can make your own based on this guide from the WHO: https://www.who.int/gpsc/5may/Guide_to_Local_Production.pdf
profquail··on U.S. bill to exempt small virtual currency transactions from CGT [pdf]
That’s known as “structuring” and is illegal:

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

profquail··on Global Wave of Debt Is Largest, Fastest in 50 Years
If you’re in the US, the legal counterparty for any exchange-traded (or OTC-traded-but-exchange-reported) is the Options Clearing Corporation (OCC). The idea is that it’s a consortium of many exchanges and broker-dealers that can absorb any counterparty risk should the party who sold you can option contract become insolvent / unable to deliver.

https://www.theocc.com/

https://en.wikipedia.org/wiki/Options_Clearing_Corporation

profquail··on Intel publishes misleading benchmarks against AMD
Maybe they could include NBASE-T nics that’d also support 2.5 and 5 Gbps speeds?
profquail··on Smart TVs sending sensitive user data to Netflix and Facebook
NewEgg — look under “digital signage” / “commercial displays”: https://www.newegg.com/Commercial-Displays/SubCategory/ID-30...
profquail··on Smart TVs sending sensitive user data to Netflix and Facebook
You can get dumb TV’s, they’re just called “digital signage”. For example: https://www.lg.com/us/business/digital-signage/lg-60UL3E
profquail··on Kei – A small and expressive dependent language
“Rewriting rules” refers to term-rewriting systems[1], which are sets of directed equations. An “undirected” equation is similar to what you see grade-school algebra class, e.g. y = ax + b; if you have the right pieces of data, you can solve the equation towards either side of the equals sign. A directed equation can only be solved in one direction. That’s important because it allows you to come up with a system of rules that, when recursively applied to a term, eventually terminate.

A “confluent” term rewriting system just means that the set of equations in that TRS has a property where, if there’s ever multiple applicable rules that can be applied, no matter which of those rules you choose to apply to a term, you eventually get to the same state (again, when the rules are applied repeatedly to a term).

Beta-reduction [2] is one of the core operations you can perform with lambda calculus? You can think of it as being equivalent to a function call; an alternate analogy is when a C compiler inlines a particular function call during compilation, it’s performing beta-reduction at that call site.

That doesn’t explain everything in the quoted text, but hopefully it helps make it a bit more understandable. If you really want to learn more about this area of CS, take a look at the book Types and Programming Languages (TAPL) [3].

[1] https://en.m.wikipedia.org/wiki/Rewriting

[2] https://en.m.wikipedia.org/wiki/Lambda_calculus#β-reduction

[3] https://www.cis.upenn.edu/~bcpierce/tapl/

profquail··on Python Is Eating the World
.NET has always had slow exception handling because it tied/ties in Windows’ Structured Exception Handling (SEH); that’s rather slow but provides e.g. detailed stack traces even for mixed-mode callstacks.

Having ported some decently large codebases from OCaml to F#, the heavy use of exceptions in OCaml (where exceptions are very lightweight by design) had to be changed to normal control flow with monads to achieve good performance in F# — specifically because of .NET’s slow exception handling.

profquail··on Arend: Theorem Prover Based on Homotopy Type Theory by JetBrains
An example of real-world verified software is miTLS: https://www.mitls.org/
profquail··on A Black Hole Engulfing the World's Bond Markets
Banks offer both fixed-rate (“locked in”) and floating-rate mortgages (where you pay the prime rate + some fixed number of basis points).
profquail··on Owl – OCaml Scientific Computing
It's been feasible to run F# on Unix for years, first via Mono, and more recently with .NET Core.
profquail··on Owl – OCaml Scientific Computing
You can read, say, the top N lines of the file and perform type inference on the column data to determine the type of the column. This is how it's done in the F# "type provider" for CSV: https://fsharp.github.io/FSharp.Data/library/CsvProvider.htm...
profquail··on U.S. Tech Companies Sidestep a Ban, to Keep Selling to Huawei
ARM is a major tech company based in Europe.
profquail··on Discrete Mathematics and Functional Programming (2016)
Or PolyML, which is another popular implementation (e.g. used in the Isabelle/HOL theorem prover):

https://polyml.org/

profquail··on AMD Ryzen 3000 announced
Have you considered using the POWER9-based Raptor Blackbird uATX board for your next build? The firmware is open, and they advertise it as a feature:

https://www.raptorcs.com/content/BK1B02/intro.html

profquail··on Vampire: First-Order Theorem Proving [pdf]
What Vampire and similar “automated theorem provers” are doing is searching for a proof of some logical statement (that you specify). That proof search is a really tough problem, so there’s a ton of research that goes into finding ways of speeding up the search e.g. through novel data structures. Proof verification —- the process of verifying the correctness of some claimed proof —- is much faster.
profquail··on Nfhttp: A cross platform C++ HTTP library natively interfacing to platforms
How does this compare to cpprestsdk?

https://github.com/Microsoft/cpprestsdk

profquail··on Git implemented in Rust
If you really needed to run Rust code on some platform LLVM doesn’t natively support, it does allow you to compile to C. Presumably you could then compile that using whatever C compiler works for your platform.

Although Rust is not as portable as C, going through these hoops would mean that —- modulo codegen bugs —- the generated C code should still be as memory-safe as the original Rust code.

profquail··on A programming language agnostic type construction and interchange language
Check out ATerms, it’s a storage (and in-memory representation) designed for storing ADTs: https://github.com/cwi-swat/aterms
profquail··on A programming language agnostic type construction and interchange language
This is an interesting idea, but I don’t see what’s different about it compared to ATerms: https://github.com/cwi-swat/aterms
profquail··on ARM and Intel have different performance characteristics: a case study
Aye, it’s PMULL, and it’s available as part of the ARM Crypto Extensions.

This patch shows that using it can result in a large performance improvement: https://github.com/randombit/botan/issues/842

profquail··on Top books discussed on Stack Overflow and other Stack Exchange sites
Maybe not a bad thing, but seems less of a strong signal of “goodness” compared to a book recommended the same number of times by different users. You might consider capping the number of times you consider recommendations for one book from a single user to something reasonable, like 3. That way you get more of a crowd consensus as to what’s really good.
← PreviousPage 2 of 29Next →