Creating an array of generics in Java

Software, , ,

I was messing around with creating a generic Bag collection in Java that’d be backed by an array. It turns out that you can’t do this for a number of interesting reasons…

In Java (and C#), arrays are covariant. This means that if Apple is a subtype of Fruit, then Apple[] will also be a subtype of Fruit[]. Pretty straightforward. That means this will compile:

Apple[] appleArray = new Apple[10];
appleArray[0] = new Apple();
Fruit[] fruitArray = appleArray;    //Spot the problem?

If you’re like me, you didn’t think too hard about this, and assumed you could do the same with parameterized types, i.e. generics. Thanksfully you can’t, because that code is unsafe. It will throw an ArrayStoreException at runtime which we’d have to handle.

Wouldn’t it be great if we could guarantee type safety at compile time?

Generics are safer

Unlike arrays, generics are invariant, which means that Apple being a subtype of doesn’t matter: a List<Apple> is different than a List<Fruit>. The generic version of the code above is illegal:

Vector<Apple> apples = new Vector();
Vector<Fruit> fruits = apples;       //Compile-time error

You can’t cast it, either:

Vector<Apple> apples = new Vector();
Vector<Fruit> fruits = (Vector<Fruit>)apples; //Still a compile-time error!

By making generics invariant, we guarantee safe behavior at compile time, which is a much cheaper place to catch errors. (This is one of the big reasons developers get excited about generics.)

So why are arrays and generics mutually exclusive?

In Java, generics have their types erased at compile time. This is called type erasure. Type erasure means a couple of things happen at compile time:

  • Generic types are boiled down to their raw types: you cannot have a Derp and a Derp<T> in the same package.
  • A method that has a parameterized type overload won’t be compile: a class with methods popFirst(Derp<T> derp) and popFirst(Derp derp) won’t compile.
  • Runtime casts are inserted invisibly by the compiler to ensure runtime type safety. (This means there’s no performance benefit to generics in Java!)

Java’s implementation of generic types is clumsy, and was done to maintain backward-compatibility in the bytecode between Java 5 and Java 4.

Other high-level languages (like C#) implement generics very differently, which means none of the three caveats above apply. Generics in full-stack implementations do net performance gains along with those type-safety guarantees.

To recap, in Java:

  • Arrays require type information at compile time
  • Generics have their types erased at compile time

Therefore you cannot create arrays of parameterized types in Java.

Further reading

Understanding the word “semantics” in the context of programming

Programming, Writing

tl;dr- It’s usually safe to substitute the phrase behaviors and guarantees into a sentence where you see the word “semantics”–and the discussion is about programming.

Longer version: New programmers often come across the word semantics, and wonder what it means. Pretty much every explanation they will read points out the distinction between syntax (form) and semantics (meaning). This is easy to grasp, but not useful for understanding the word in the context of a sentence like: The stylistic choices should typically be driven by a desire to clearly communicate the semantics of the program fragment.

Go ahead and substitute the word “meaning” there. It isn’t much help unless you’re already an experience developer.

So to that end, new programmers… if ever you come across this word, it’s generally safe to substitute the phrase behaviors and guarantees in its place. This may help you understand the semantic intent (ha!) of the writer a little more.

Recursion as sophisticated GOTO?

Programming

Suppose you write a simple program to play a number guessing game: “I’m thinking of a whole number between X and Y…” where the user attempts to guess the number in order to win. Failures that require feedback to the user come in three main flavors:

  1. The user guessed incorrectly
  2. The user’s guess was out of range
  3. The user did something silly, like enter a non-integer value

The do..while form

You can do this with a loop, of course. A do..while loop seems like a natural choice here. What I don’t like is the validation and user feedback in the while clause. You’d call out to a method that hides all of the validation logic, and returns true or false. This is OK, but that boolean method will have a side effect, i.e. feedback to the user.

do {
    //increment guess count
    //ask for input
    //read in input
} while (
    //input is wrong
);

The recursive form

An alternative implementation might use recursion:

static void elicitGuess() {
    //increment guess count
    //ask for input
    //read in the input
    //validate input inline
        //Failure:
            //display relevant feedback
            //elicitGuess()
        //else return
}

I find this second way to be more natural and readable. But it also feels like the wrong thing to do, though I can’t articulate why. Maybe it’s because any time I’ve seen code that followed this kind of pattern, I’ve seen it written using loops.

Thoughts?

Memory access patterns in high-level languages

Programming,

Like many developers that work in high-level languages, I think don’t spend a lot of time thinking about memory access patterns. This is probably a good thing… for the most part, worrying about this is premature optimization. But there are times when it matters, and the compiler won’t magically “optimize” it away for you, even if you have optimizations turned on:

Code

class MemoryAccessPatterns
{
    static void Main(string[] args)
    {
        var timer = new Stopwatch();
 
        timer.Start();
        for (var i = 0; i &lt; 25; i++)
        {
            doFast();
        }
        timer.Stop();
        Console.WriteLine("Fast array: {0}", timer.ElapsedMilliseconds);
 
        timer.Restart();
        for (var i = 0; i &lt; 25; i++)
        {
            doSlow();
        }
        timer.Stop();
        Console.WriteLine("Slow array: {0}", timer.ElapsedMilliseconds);
        Console.ReadKey();
    }
 
    private static void doFast()
    {
        var fast = new int[5000, 5000];
        for (var i = 0; i &lt; 5000; i++)
        {
            for (var j = 0; j &lt; 5000; j++)
            {
                fast[i, j]++;
            }
        }
    }
 
    private static void doSlow()
    {
        var slow = new int[5000, 5000];
        for (var i = 0; i &lt; 5000; i++)
        {
            for (var j = 0; j &lt; 5000; j++)
            {
                slow[j, i]++;
            }
        }
    }
}

Results

Release x86, optimizations on:
Fast array: 3829
Slow array: 8495

Release x86, optimizations off:
Fast array: 4357
Slow array: 8675

Release x64, optimizations on:
Fast array: 5074
Slow array: 10445

Release x64, optimizations off:
Fast array: 5954
Slow array: 10781

I tried this out after seeing this discussion thread on Quora this morning.

How to fix broken iCloud photostream sync on Windows

Software, , ,

Symptom

  • Your iPhone is set to back up your photos to iCloud
  • iCloud on your Windows machine is configured to download your photos
  • iCloud isn’t downloading your photo stream.

Fix

  1. Open the Task Manager by hitting Ctrl+Shift+Esc
  2. Click the Processes tab
  3. Click Name to sort the processes by name
  4. Find the Apple Photostreams Uploader and Apple Photostreams Downloader processes. End both of them.
    • In Windows 7, these will be called ApplePhotostreamsUploader.exe and ApplePhotostreamsDownloader.exe
  5. Hold down your Windows key, and hit R to open a Run prompt
  6. Type %appdata% and hit Enter
  7. Open Apple Computer > MediaStream
  8. Delete everything in the directory
  9. Log out of your Windows account, and log back in (or just reboot, if you find that easier)
  10. Once you’ve logged back into your Windows account, open the iCloud control panel again
  11. If the Photos checkbox is empty, check it
  12. Click Options, and make sure the photo options are configured how you want them
  13. Click Apply

In a few moments, your photos should start downloading.

Notes

iCloud isn’t very smart about a great many things. Here are a few:

  • If you changed the location of your downloaded photos, it will redownload what it can, creating duplicates.
  • In the iCloud 2.x days, your downloads and uploads were usually split into a Downloads and Uploads directory, and you could change the directories if you wanted. That’s not true anymore. Instead, iCloud 3.x creates a “My Photo Stream” directory, and sticks your downloads in there. Anything you’ve shared with other people, or that other people have shared with you goes into “Shared”. If you want to push a photo from your computer to iCloud, put it into Uploads


If you found this post useful, please consider donating $2

How to get Medicare to reimburse you for seeing a non-Medicare doctor

Health, ,

This post explains how to get reimbursed by Medicare directly, and is applicable to people who have Part B coverage. I have included the exact forms and letters that I used to get reimbursed by Medicare directly; you simply need to fill in the blanks. These forms can also be used if patients see their provider “virtually” (i.e. by phone or video conference).

The problem

I have a family member that gets reimbursed directly by Medicare for out-of-pocket costs that she pays herself. Several unusual criteria apply to our case… This family member:

  • Has a health care provider that does not accept Medicare
  • Lives in a rural, health professional shortage area (HPSA)
  • “Sees” her provider virtually. Medicare refers to these types of visits as telehealth, and they are reimbursed at the same rate as normal, in-person visits; there are no special telehealth billing codes. To be eligible for telehealth reimbursement, you must meet certain criteria.
  • Uses me as her Social Security Payee, which makes her my legal dependent. (I have to do everything on her behalf.)

Despite all of these special circumstances, we’re able to get reimbursed by Medicare directly, which is $3-4,000 a year. We had to appeal twice on our first attempt at getting reimbursed. The language and documents I have distilled below reflect this. It helps to very, very clear about why your request is valid.

Appeal letter: Word version | Google document

Need an example of an appeal letter? Post in the comments below, and I’ll clean mine up.

Supporting documentation

  1. Fill out a “Patient request for medical payment” form
  2. A signed, dated letter from your provider that states that they refuse to submit claims to Medicare, and that they are not (and don’t wish to become) a Medicare provider (Microsoft Word | Google Doc)
  3. A copy of an itemized bill for services rendered in the last however many months. This bill should contain the date of service, cost, and the service rendered. Once you’ve got the reimbursement process down, you should submit a reimbursement request every 3 months or so. (Microsoft Excel | Google Spreadsheet)
  4. A request to be reimbursed that references the pieces of documentation above. (Microsoft Word | Google Doc)
    • For telehealth reimbursement only: A letter stating that there are no suitable providers in a 500 mile radius of the patient’s address, or that the patient is in an HPSA-designated region. I included this information in the reimbursement request itself (#3). By the way: telehealth visits are generally only applicable to mental health services.

You do NOT need to include diagnostic information.

Ways you may need to change the included sample letters

  • Change the billing codes so they’re relevant for your case.
  • Change the provider’s name and credential information.
  • Look for stuff in the letters that looks <Like this>, and replace it with information relevant to your case.
  • If you are doing this for yourself or for someone who is not a dependent: Each of the sample letters is written by me on behalf of a legal dependent. If this doesn’t apply to you, modify each document so it’s written from the perspective of the patient themselves: use “I”, “me”, etc., and have them sign it.
  • If you are not trying for telehealth reimbursement, remove the sections that talk about being in a health professional shortage area and/or telehealth references.
  • Make sure the Conclusions section in the request letter is relevant. For example: my version includes comments about telehealth; yours may not, so delete them. Make sure they make sense for you.

Send the paperwork certified mail

You won’t be sending your 3-4 pieces of documentation to Medicare. You’re going to be sending them to a Medicare Carrier, which varies by state. Find yours here.

We did not send our first appeal certified mail, and it got lost. This cost us three months. Save yourself the time and aggravation, and send your documentation certified mail.

Be prepared to wait

It took me over a year to finally get reimbursed by Medicare. It took three incomplete attempts, and two appeals before I won my case. You may not succeed the first time… but keep at it. If you can push through the bureaucratic apathy, you will probably succeed.

Good luck! Ask any questions in the comments below, and I’ll do my best to answer them. Getting Medicare to reimburse you for covered expenses is NOT easy.

Update 2014-09-06: The second round of reimbursements went off without a hitch. No appeals, no additional documentation. Just a large check a little over a month after the reimbursement request was filed!