@pervognsen@mastodon.social avatar

pervognsen

@pervognsen@mastodon.social

Performance, compilers, hardware, mathematics, computer science.

I've worked in or adjacent to the video game industry for most of my career.

This profile is from a federated server and may be incomplete. Browse more on the original instance.

pervognsen, to random
@pervognsen@mastodon.social avatar

"The algorithm uses exactly the same terminology and is presented in bottom-up form. (If you prefer top-down design, please read the rest of this section backwards.)"

pervognsen, (edited )
@pervognsen@mastodon.social avatar

These classic-era structured programmers really loved their sentinels and really hated their gotos/breaks/returns. You can't tell me that it's easier to prove the correctness of this with Hoare-Dijkstra-style assertions than if you had an early return; assertions flow across control flow edges just fine, and when you have multiple control flow predecessors your precondition is the logical disjunction of those in-flowing assertions. Bob Floyd used Hoare-style triples for flow charts before Hoare.

pervognsen,
@pervognsen@mastodon.social avatar

@regehr It's a global constant: w for width, x is an array [0..w], keeping in mind that this is inclusive Pascal arrays so it actually has w+1 entries.

pervognsen, to random
@pervognsen@mastodon.social avatar

Why uniform randomized testing might not be the best idea for validating that your base b = 2^64 arbitrary-precision long division implementation has properly implemented the correction step of quotient digit estimation:

pervognsen,
@pervognsen@mastodon.social avatar

I guess the "glass half full" angle on this is that in a non-adversarial situation, you might be able to get away with it. I encourage you to build mass-market divider circuits based on randomized testing; that worked well for Intel.

pervognsen,
@pervognsen@mastodon.social avatar

@TomF I was referring to the Pentium FDIV debacle. AFAIK they primarily validated the algorithm with randomized testing.

pervognsen, to random
@pervognsen@mastodon.social avatar

This classic blog post resurfaced on the Rust subreddit today after someone posted that they wished ownership had been explained to them with a metaphor about pirate treasure chests.

https://byorgey.wordpress.com/2009/01/12/abstraction-intuition-and-the-monad-tutorial-fallacy/

'But now Joe goes and writes a monad tutorial called “Monads are Burritos,” under the well-intentioned but mistaken assumption that if other people read his magical insight, learning about monads will be a snap for them. “Monads are easy,” Joe writes. “Think of them as burritos.”'

pervognsen,
@pervognsen@mastodon.social avatar

(I think Yorgey is overstating the extent to which everyone needs to begin with the concrete and move to the abstract. By programmer standards, I'm probably more on the side of learning quickest from looking at the general case first, and when I spent most of my time around other mathematicians in college I met people who had a really hard time "getting it" from examples but could much more immediately grasp abstract concepts if presented directly.)

pervognsen,
@pervognsen@mastodon.social avatar

@zwarich One of my favorite example-driven math books is Shafarevich's Basic Notions of Algebra but I've never been able to tell who it was intended for, exactly. Right after giving the definition of a ring homomorphism he will give you ten pages of examples like this.

pervognsen,
@pervognsen@mastodon.social avatar

@zwarich You still have trouble understanding what a ring homomorphism is, second-year student? Maybe this one helps.

pervognsen,
@pervognsen@mastodon.social avatar

@zwarich I'm pretty sure it's not intended as a pedagogical text, but for someone who already knows most of the material it's a treasure trove of examples and connections to other parts of mathematics.

pervognsen,
@pervognsen@mastodon.social avatar

@pkhuong @zwarich The other thing is that it's impossible for almost anyone to learn a non-trivial thing sufficiently in "one pass". So if you're psychologically stuck on wanting to completely understand everything before proceeding, you will never get to understanding. One of the joys of learning is that you get to revisit the basics throughout your life and understand them a little bit better each time. But especially with your first encounter, you just need to trust the process.

pervognsen,
@pervognsen@mastodon.social avatar

@pkhuong @zwarich You see this even with basic arithmetic. How many people (good math students) really understand long multiplication, never mind long division, to the extent that they could explain how it relates to the more primitive concept of addition and multiplication as counting from first grade? But kids at that age seem more willing to just go along with it. It's when you get older that people (especially adults) get stuck on wanting to understand things before letting themselves learn.

pervognsen,
@pervognsen@mastodon.social avatar

@steve @pkhuong @zwarich I already know this is going to be about 2-cochains, Steve.

pervognsen,
@pervognsen@mastodon.social avatar

@steve @pkhuong @zwarich I learned that factoid from reading old James Dolan posts on sci.math.research!

pervognsen,
@pervognsen@mastodon.social avatar

@steve @pkhuong @zwarich Anyway, my point wasn't so much that people don't understand multiplication and especially long division, but that if we had applied the standard of wanting to deeply understand things before going through a learning process we would all still be stuck at long multiplication, probably. But I do have a personal anecdote about long division that shocked me, when I realized after already being in university for math that I hadn't understood the role of quotient estimation.

pervognsen,
@pervognsen@mastodon.social avatar

@steve @pkhuong @zwarich Basically I was trying to figure out how to implement long division for arbitrary-precision arithmetic but with base 2^32 so you can use machine arithmetic as an efficient basis set of operations. And that's when you realize that small bases let you kind of brush the question of quotient estimation under the rug to the point where I hadn't even noticed it was happening in decimal long division.

pervognsen, (edited )
@pervognsen@mastodon.social avatar

@steve @pkhuong @zwarich And that's when I finally folded and looked it up in Knuth and of course it's quite subtle: you can get away with looking at 3 leading digits of the dividend and 2 leading digits of the divisor, if you're in a power-of-two base, if you re-scale so the divisor's leading digit's MSB is 1, if you're okay with sometimes being off by 1 in the quotient estimate (which can be detected and fixed in one step). Probably got that wrong, but in any case it's not trivial.

pervognsen, (edited )
@pervognsen@mastodon.social avatar

@steve @pkhuong @zwarich "Guess (and verify) the next quotient digit" sure works a lot better in base 10. Of course you can do binary search in base 2^n to guess more efficiently but that's effectively reducing to base 2, which is the ultimate cheat move.

Much later I found this technical note by Per Brinch-Hansen who has a stepwise discussion and development of how to do it. I believe he recommends (for tutorial purposes) a less tight estimate that can be off by 2 or 3 in the worst case.

pervognsen,
@pervognsen@mastodon.social avatar

@steve @pkhuong @zwarich Multiple-Length Division Revisited: A Tour of the Minefield (1992), Per Brinch-Hansen, https://surface.syr.edu/cgi/viewcontent.cgi?article=1162&context=eecs_techreports

"Only a handful of textbooks discuss the theory and practice of long division, and none of them do it satisfactorily. This tutorial attempts to fill this surprising gap in the literature on computer algorithms."

pikuma, to random
@pikuma@mastodon.gamedev.place avatar

Well, it finally happened. An Off-By-Two error...

pervognsen,
@pervognsen@mastodon.social avatar

@pikuma Believe it or not, I had one of those today, too. I was writing some C glue code and needed a +1 to the buffer size for the zero terminator and then there was a regular off-by-one error stacked on top of that. Off-by-two is not that uncommon in C code involving zero-terminated strings.

danluu, to random
@danluu@mastodon.social avatar

Interesting to see users working around the lack of tactile buttons in some modern cars:

pervognsen,
@pervognsen@mastodon.social avatar

@danluu Once again happy that the most expensive car I've owned is a new Honda Fit/Jazz for $20,000 or so. Keep all that crap far away from me.

pervognsen, to random
@pervognsen@mastodon.social avatar

This came up in another thread today but I figure I'd throw a brief comment to the timeline. The concept of "grace periods" where you separate the logical and physical deletion of resources is something you see in RCU, EBR, QSBR, etc, but it's just as useful in single-threaded code where you only have pseudo-concurrency through subroutine calls. Like the age-old pattern of deferring deletion until the end of the game loop, or autorelease pools in Objective C which get drained by the run loop.

pervognsen,
@pervognsen@mastodon.social avatar

@zwarich If you're rebuilding the old table and the previous old table was [0..old_watermark] and the next old table is going to have [0..new_watermark] then a nice trick is to build a much smaller hash table for just the ID range [old_watermark..new_watermark] and then do the Robin Hood sorted-hash merge of that with the previous old table.

pervognsen, (edited )
@pervognsen@mastodon.social avatar

@tobinbaker Is it a stretch to call that EBR? With EBR the collector advances the epoch and then waits for all the readers to (1) enter a read-side critical section and acknowledge that they've seen the new epoch and (2) leave that read-side critical section. I.e. there's a collector -> reader -> collector round-trip of information flow. With trailing log truncation you don't really have anything like that?

pervognsen, (edited )
@pervognsen@mastodon.social avatar

@tobinbaker And in EBR you also have a third role, the writer, who is orphaning old items and thereby producing garbage that needs to be cleaned up eventually, but not so soon the readers will be affected, by attaching it to an epoch. So it's not enough to have one-way information flow/passive observers.

But yeah, certainly the "min" approach works well for linear/circular buffer truncation. You also see this in LMAX's Disruptor.

  • All
  • Subscribed
  • Moderated
  • Favorites
  • •
  • anitta
  • mdbf
  • everett
  • Youngstown
  • tacticalgear
  • slotface
  • rosin
  • Durango
  • hgfsjryuu7
  • kavyap
  • vwfavf
  • thenastyranch
  • DreamBathrooms
  • PowerRangers
  • Leos
  • magazineikmin
  • ethstaker
  • modclub
  • InstantRegret
  • osvaldo12
  • GTA5RPClips
  • ngwrru68w68
  • khanakhh
  • cubers
  • normalnudes
  • cisconetworking
  • tester
  • provamag3
  • All magazines
    •