Browsed by
Category: Problem solutions

Optimal Battleship

Optimal Battleship

Nick Berry, president of DataGenetics, meticulously analyzes different strategies to play the classic board game Battleship (he also has done Chutes & LaddersCandyland and Risk)

It’s a great example of how computer scientists often work. He explores a host of techniques and analyzes the results by calculating how often you’ll get a perfect game, median number of guesses, and how bad it gets in the worst case.

He examines 4 major strategies:

  1. Pure random searching
  2. Hunt and Target – Hunt randomly until you get a hit, then proceed methodically to sink the hit ship.
  3. Hunt and Target with parity – since the minimum length of a ship is 2 units, you need only search even or odd squares
  4. Hunt and Target with parity combined with a probability density function.

His fourth approach is the most fascinating. The system calculates every possible configuration of the remaining ships, and then sums up the probability of a ship on each square. At the beginning, all the squares are basically equally probable, but as more and more guesses are made, the number of possible configurations decreases. If you continually calculate the sum of these possibilities, pick the square with the highest probability and repeat this process, you get significantly better results.

How much better? Purely random guessing gives you a median of 97 moves. Using parity with the hunt+target method averages 64 moves. But using the probability density function increases that to a staggering 42 moves on average.

Turns out, I discussed the use of this kind of probability density function by speedrunners who used the same technique to beat the splosh-kaboom minigame in the Legend of Zelda Wind Waker.

Copyright free chill/ambient music

Copyright free chill/ambient music

Are you slapping together that next big startup idea pitch reel? Want to become a streamer or Youtube star? At some point, you’re going to need some background music to fill dead spaces, set the tone, etc. But how does one avoid a dreaded DMCA takedown?

While there are lots of online shops that will sell you royalty-free music, I usually find myself running off to find the amazing amounts of free stuff out there – like this.

Hooking 2 modems together without an active phone line

Hooking 2 modems together without an active phone line

Land lines are getting hard to find these days. Almost as hard to find as old modems.

Back when I was a kid, I wanted to play a network game between two computers in my own house. I achieved this by hooking the modems up in a daisy chain. One modem plugged into the phone line like normal. On the ‘out’ port of the modem, I ran another line from it to the IN line of the 2nd modem. I then had the 2nd modem call our home phone number – which caused our phone to ring, the other modem picked up, and they made their normal connection sounds and connected! I could then unplug modem 1 from the phone line and the computers stayed in contact without issue.

At the time, I thought I needed a dialtone generator or line generator. Little did I know, I could have done it with a simple 9 volt battery and the right sized resistor. Skip along to 8:25 to see how to wire them together.

TP-Link OneMesh Network configuration and speed testing

TP-Link OneMesh Network configuration and speed testing

I recently bought the highly recommend TP-Link AC1750 Smart WiFi Router when my old one started acting up and generally being horribly out of date. Modern routers have some great features.

I also have some TP-Link RE220 range extenders (repeaters). The question was – how should one set these up? There’s a lot of different configuration options.

Turns out that Behfor’s channel on YouTube has answered my questions with some excellent testing. The first video covers the RE220, the second video covers the different ways to set these up using OneMesh – and which are the best for both connectivity and for throughput.

Beating splosh-kaboom minigame in Legend of Zelda: Wind Waker

Beating splosh-kaboom minigame in Legend of Zelda: Wind Waker

It took them about 10 years to build this speed running tool, but here it is. How it helps you win is even more fascinating than the minigame itself. Random number generators on consoles are notoriously simple and have been exploited for some time – but this takes it to a whole new level.

It’s a beautiful example of how a computer scientist would break down and solve a problem. It’s also a perfect example of why cryptographically secure random number generators are essential to computer security.

I think I might use this question in future interviews…

Understanding SSD form factors and interfaces

Understanding SSD form factors and interfaces

SSD’s have been transformative to the entire storage market. The use of solid state memory instead of spinning platters changed how thin, light, rugged, and power efficient modern laptops are.

However, understanding them well enough to upgrade your system has not been easy. Turns out, there have been not only a bunch of different form factors, but interfaces as well. Most guides I found do a terrible job explaining the differences – and often use form factor and interface types interchangeably in confusing ways.

Lets start our journey in understanding different SSD form factors and interfaces with 2 important pieces of terminology: Form factors and interfaces.

Form factor: The form factor is the physical dimensions for the drive. The form factors tells you if the drive will physically FIT in the system. They tell you nothing about whether the drive will actually WORK with your system – or even plug in.

It is possible to find two drives that have the same form factor, but be based on very different physical or interface technologies. For example: it’s possible to find a 2.5″ hard drive that uses traditional physical platters or solid state memory. It’s also possible to find 2.5″ drives that use the SATA interface or IDE (or many others too).

Interface: The interface of a drive tells you how the drive communicates and transmits data with the rest of the system. The interface is often (but not always) revealed by the type of power/data plugs that the drive has.

It is possible to buy a drive with the right interface for your system, but find out it won’t physically fit in the system. It is also important to know that, just like USB ports, some interfaces have the same physical plugs, but support many different speeds of data transfer. It’s possible to buy a drive with the right interface, but find that it’s nowhere near as fast as the interfaces allows (such as plugging in a USB 1.x device to a USB 3.x port).

Storage medium/technology: The third, and final important factor is how the data is physically stored. There are 2 main types of storage in a computer – volatile and non-volatile storage. Data in volatile storage (main computer memory) is wiped out completely when the power goes off. Non-volatile storage stays around. Since the earliest days of the computer, there was always a need for non-volatile storage.
In the 50’s and 60’s, the most common non-volatile storage medium was punch cards. They were simple card stock with holes punched in them. We then moved to tape drives that utilized large spools of magnetic tape. We then moved to hard drives and floppy disks that utilized circular platters that were coated with magnetic material. Drive heads moved over the surface as the drive spun, and read the 1’s and 0’s. The next major advance was the use of solid state memory for storage. USB sticks used flash memory. More recently, we have seen the introduction of solid state drives that utilize much faster NAND flash memory.

The ‘Standard’/Legacy Form Factors

Lets dig deeper into these topics and starting with form factors.

These drives look very much like the old drives of days gone by. They came in a standardized 5.25″, 3.5″, 2.5″ and 1.8″ drive sizes. This size refers to their width to fit into physical drive bays located in your computer case. You can buy both SSD, floppy, or older platter sized drives in these form factors. It’s also often possible to buy display units and USB or flash drive readers in this form factor.

USB 3.0 and audio port kit that mounts in a 3.5″ drive bay

These form factors are legacy from older platter and CDROM drive dimensions; but kept because it made mounting and replacing drives easier for PC manufacturers. Desktop systems often have several 5.25″ drive bays for CDROM/Blu-ray or other optical disk formats (though back in the day, there were even 5.25″ hard drives and 5.25″ floppy drives). 3.5″ and 2.5″ drive bays can be found in desktops and laptops. As laptops shrunk, hard drive sizes did too. 1.8″ drive sizes were the smallest things got before we moved to even smaller formats that didn’t need 4 point physical mountings that spinning drives did.

As things miniaturized, the need for even tinier form factors became paramount. Here are some of those.

PCI Express Mini/Mini-PCIe/mSATA/MO-300 (full or half size) Form Factor

  • Physical size: 50.8mm x 29.85mm
  • Connector type: 52-pin card edge connector (split into 16-pin & 36-pin sections)

This form factor isn’t very common for storage and is something of a halfway step between platter drive form factors and M.2. You’re likely to encounter it in early laptops. This form factor comes in two varieties: full size and half size.

Great care must be taken with this form factor. Both mSATA and mini PCIe cards have the exact same form factor AND connector type – but your laptop may or may not support both interface types.

Half slimSATA/SlimSATA (MO-297) Form Factor

  • Physical size: 39.8mm x 54mm
  • Connector type: 22-pin standard 2.5” SATA SSD connector

This is a rarer format these days. This form factor comes in half and full sized versions. It can be identified by the fact it uses the standard 22 pin SATA connector.

M.2 Form Factor – Keys and slots

M.2 is the latest, most modern form factor for devices. M.2 was introduce as the Next Generation Form Factor, but I have only seen it referred to as M.2. You can find not only storage in M.2 form factor, but also WiFi, bluetooth, GPS, and other devices. This form factor comes with three important form factor parameters: length, width, and keying.

The vast majority of M.2 devices typically come in the three sizes above, which may be deduced from the card names —2242, 2260, and 2280. The first two digits (22) represents the width in millimeters (mm), while the next two digits represent the length, also in mm.  It is possible to have a wide variety of widths and lengths – but the above sizes are the most common for storage and user devices.

Next up is their “key” type. Believe it or not, there are 12 different kinds of M.2 keying, but the most common for storage are B, M, and B+M.

In this case, you can often determine the interface type by the physical key-ing. B+M (which can fit in socks for B-keyed and M-keyed modules) are usually SATA interfaced. M.2 devices that use the NVMe interface are often only M keyed.

Interfaces

So, now that we’ve discussed if a drive will physically fit in your system, lets talk about how the data flows between your computer and the device. To avoid confusion, almost every interface has its own, unique type of physical data connector.

MFM/RLL/IDE

Wow – these are some old interface types. MFM/RLL are some of the first hard drive interfaces used in the late 80’s and early 90’s. By the 90’s, IDE (sometimes called parallel ATA) had taken over. No modern systems have used these interfaces in almost 20 years.

Serial-ATA/SATA

SATA is probably the most common interface on the market today. You can find it on everything from older platter drives, SSD drives of many form factors, Blu-ray drives, CDROM drives and burners. It was a great replacement for the older IDE interfaces of the 90’s.

SATA has gone through numerous upgrades over the years as speeds have increased. Most modern drives today use the latest iteration – SATA III – which delivers 600MB/s peak performance. SATA maintains very good backwards compatibility with older versions of SATA. Due to performance of the underlying storage media, most SATA III SSD drives get 500-550MB/s. SATA III drives that use physical spinning platters can usually only get to 100MB/s due to their physical speed limitations (limitations of the read heads/platters). So just moving from a platter SATA III drive to a SSD SATA III drive can often yield you around a 5x speedup.

The important point about this interface is to know that if your device uses the SATA III interface, you won’t be getting faster than 600MB/s. This can be confusing because some M.2 storage media has both NVMe and SATA III interface support. But if your motherboard only supports SATA III M.2 devices, you’re only going to get the slower SATA III speeds. So be sure you check your motherboard specs and ensure you are using the right ports on your motherboard or you could be wasting a lot of money on performance you won’t be getting.

Additionally, you might think you are upgrading when you get rid of your 2.5″ form factor SSD drive that has the classic SATA III connectors for your fancy new M.2 form factor drive. But if that new M.2 drive uses the SATA III interface internally, you will be getting pretty much the same performance. So if you want NVMe speeds, make sure both the storage device AND your motherboard support NVMe. Otherwise, you’re probably getting SATA III speeds.

NVMe

NVMe stands for the Non-Volatile Memory express interface. The Non-Volatile Memory Host Controller Interface Specification (NVMHCIS) is an open logical device specification for accessing non-volatile storage media attached via the PCI Express (PCIe) bus.

Interfaces that were designed during the era of physical platter drives (IDE/SATA/etc) have very different latency profiles and very linear/serial input and output characteristics. These interfaces weren’t designed to exploit the unique massively parallel performance characteristics of non-volatile memory storage. The NVMe interface was designed to capitalize on the low latency and massive internal parallelism of solid-state storage devices by having a deep queue system.

By its design, NVMe allows host hardware and software to fully exploit the levels of read and write parallelism possible in modern SSDs. As a result, NVMe reduces I/O overhead and implements performance improvements like multiple long command queues, and reduced latency. 

How fast is NVMe? Well, some drives advertise throughput rates up to 3500MB/s (Samsung 970 Evo Pro) – which is almost 6 times the speed of SATA 3 SSD’s. This makes them around 35 times faster than platter-based hard drives.

PCIe

PCIe drives are the kings of performance right now because they’re using the main interface bus of the system as opposed to through a storage protocol like IDE/SATA/NVMe. These devices are usually expensive because they carry additional development costs and use much faster memory. They must also write their own software/hardware layers to convert PCIe protocol read/writes to solid state memory access.

While PCIe devices have theoretical maximums that are far in excess of other drive interfaces, most typically interface via PCIe 1.x or PCIe 2.x specifications – meaning they have maximum 250-500MB/s rates. But devices like Optane memory can get up into the 1000’s of MB/s range. Early Intel Optane memory drives used PCIe because that interface was the only one that could get the to the 2800MB/s range before NVMe.

Putting it all together

So, now we can put these things all together to help us understand how the different combinations work; and why people often confuse performance when they are not clear about both interface and form factor

Form factorInterfaceSpeed
3.5″/2.5″/1.8″ platter-based hard driveIDE 5MB/s to 133MB/s (ATA100/133)
3.5″/2.5″/1.8″ platter-based hard drive SATA3100MB/s typical
3.5″/2.5″/1.8″ Solid State Memory hard drive SATA1/2/3 150/300/600 MB/s max
M.2 Solid State DriveSATA1/2/3 150/300/600 MB/s max
mSATA (typically SATA1)SATA1/2/3150/300/600 MB/s max
PCIePCIe 1.x, 2.x, 3.x, etc250MB/s, 500MB/s, 1GB/s, etc
M.2 Solid State DriveNVMeUp to 3500+ MB/s

Now it’s more clear why one needs to pay attention to the form factor AND interface. The form factor can give us hints as to what interface is used, but is not a sure-fired way to know the performance characteristics.

You could have a 3.5″ drive that is IDE, or a platter-based SATA III, or even a SATA III based SSD. While each one is almost identical in physical size – each has almost an order of magnitude performance difference between the previous. A PCIe device might use PCIe 1.x and get 100MB/s or be as fast as an NVMe based M.2 drive if it’s PCIe 3.x. A mSATA/mini PCIe device might give you 150/300/600MB/s if it’s SATA1/2/3, or 250MB/s, 500MB/s, or 1GB/s if it’s using the PCIe interface.

One of the more common current difficult ones is reading advertisements that tout M.2 drives. Many do not clearly advertise the internal interface. If they do not say it is NVMe, then you should assume it is SATA III. As we have seen, a M.2 drive that has an internal NVMe interface might make it up to 6x faster than the same one with a SATA III interface internally.

Next up:

Now that we understand form factors and interfaces, one can move on to understanding the memory technologies behind SSD drives. There are many different kinds of memory that affect performance just as greatly as interface. Most SSD’s are designed with MLC, TLC, or QLC memory configurations. Even newer is XPoint memory used in Intel’s Optane drives.

Each of these memory technologies has performance characteristics on top of the limitations of their interfaces. Some of technologies lead their drives to become slow once the drive is mostly full, some start slowing when the drive is even half full. Some have longer MTBF reliability while others statistically fail much earlier. In some cases, different controller hardware can do much better or worse jobs with these inherent limitations.

But that might be a talk for another article…

Resources:

Interfaces:

Form factors: