Sunday, November 29, 2020

Does It Matter How Fast the Code Is?

I’ve been having a lot of fun playing with code lately. One of the things I have been experimenting with is cryptography (See Tiny Book of Simple Cryptography) For one project I wanted to create a string of ones and zeros to represent the binary value of letters. I quickly came up with three ways of doing this. I know that are probably many more ways than that. But for now I have some that work and one of them I really like.

Which one is best? Well, that depends. Which one is the fastest? That depends as well. I think I know which one is fastest. It uses the bitwise & operation which generally is pretty quick. One used the Math.Pow function which I suspect slows things down quite a bit. The third uses nothing fancy at all and could easily be coded by someone with only a little programming knowledge. I suspect it is the middle in speed/ Does the speed matter though?

In this application , probably not. The bottleneck in performance is going to be in the I/O not the calculations. The performance of this function is lost in the noise.

What probably matters more, if one is looking to define “best”, is which algorithm is easier to understand..

I learned this lesson one day back when I was writing code for a living. We were doing a formal code review of my code and I had written what I thought was a very clever piece of code that was pretty efficient. The review made me rewrite it using code that was no where near as clever or interesting. It was, however, a lot easier for someone new to the code to understand. And that was more important.

Now there are applications where performance is critical. I remember working with a company building a system  to collect weather data. They collected a huge amount of data is a very short period of time. They were actually comparing the instruction execution times of various machine language instructions to pick the computer they were going to buy. That’s pretty exceptional though.

To complicate matters even more, today’s optimizing compilers are very smart. It is rare that a person coded Assembly language program can outperform code generated by an optimizing compiler. I was involved in actual benchmarks of this in the 1980s and things are improved since then. Take these two pieces of code:

if (foo % 2 == 1)

label1.Text = "Odd";

if ((foo & 1)==1)

label2.Text = "Odd";

Which one is faster? You may think the second one is faster. You might be right. On the other hand, a really smart compiler by generate the same low-level code from both of them. Unless you were on the compiler writing team you probably don’t know. Even if you have the source code for the compiler do you really want to spend the time to see how it is optimized?  You couple probably also look at the generated code but is that worth it either? Not generally.

The first example is clearer. A number of my friends who write code for a living tell me that is what they would use. Because it is clearer and understandable by more people it is not worth worrying about an optimization that may already be taken care of for them by the compiler.

Once upon a time it mattered a great deal if one iterated though a two dimensional array by column first or by row first.  One had to know which was faster and do it right. Today, compilers take most of the worry about this away from us. We can do it in the way that seems more logical for us and for the application.

One of my friends who has worked on compiler development teams tells me that conversations about this sort of optimization are frequent there. People working on compilers have the time and the experience to make compilers smart. I’m pretty sure more of them (the people and the compilers) are smarter about code optimization than I am.

That doesn’t mean we can ignore performance. I’ve seen some beginner code that is horrible in performance. But still there are trade offs. I once wrote a very slow program that I ran once a month. I thought about a way to optimize it that would cut a minute or two off of the run time. It would have taken me an hour to code and that was a lot more time than it would have saved me. Turns out a faster computer a few months later ran the inefficient code a lot faster anyway.

Honestly, though discussion optimization and performance can be fun for a certain class of geek. Geeks like me.

Sunday, November 22, 2020

The Making of a Computer Science Teacher

There is quite the conversation going on in the private Computer Science Educators group on Facebook about teacher preparation for CS educators. This is a very interesting group for CS educators BTW. Join if you are on Facebook. I link to some specific articles at the end.

It’s a lot more complicated question than it might appear. There is the argument about what CS educators need to know to teach CS effectively. Is something better than nothing or is not enough going to mean poorly prepared students? Given all the complaints I have heard from university people about high school students being taught CS wrong (what ever that means) I tend to believe that CS educators should have a lot more depth of knowledge than the courses they are teaching. Definitely more depth than their students will get from the course. We expect this from teachers of other subjects (for the most part – see highly qualified teacher).

As to preparation, and its close cousin – certification – we are dealing wtih three main types of people who need preparation to teach CS.

  • Teachers of other subjects
  • CS experienced people moving into teaching
  • Career beginners who are not previously teachers or CS people

They all need something different. I have heard people say that a good teacher can teach any subject after learning some content knowledge. I would argue that teaching CS is different from teaching most other subjects. A teacher needs to know how to teach computer science. We've been fortunate over the last decade or two that some serious research in how to teach CS has been done. CS teachers need to know what has been learned about HOW to teach.

Teachers of other subjects also need some solid content knowledge. Topping out at the content involved in AP CS Principles and AP CS A (the top high school cs courses) is not enough. Well, not for high school CS teachers. Students are going to ask deeper questions than what is required and you can only get by with “well, let’s look that up” so often before people start to wonder if you know what you are doing.

How much do you need? And this goes for people new to teaching as well as just new to teaching CS. That’s a struggle. I don’t think you can get it in two one semester courses let alone a couple of weeks worth of summer workshops. Two semesters of programming is probably the minimum for that aspect. In the first one a person learns a programming language and a start of how to solve problems. It takes a second course to really become a programmer. Of course there is a lot more to computer science than programming. Vocabulary, networking, algorithms, security, CS ethics, and well, if your have taught AP CS Principles you get the rest. So three or four semesters of real CS.

Everyone who teaches CS including those new to teaching and those career changes needs a course or two (or three) if pedagogy. A focus on teaching CS for sure but also some work on test development and evaluation and classroom management. Do they teach classroom management in regular education programs? CS has some interesting complications involving students playing on the internet and messing with lab computers.

I also think that CS teachers, especially now when there are seldom multiple CS teachers in a building, need to learn about external resources. Social media, CSTA, summer workshops and conferences, StackOverflow, and generally how to build a network to support your growth as a CS teacher.

To prepare to be a great CS teacher is going to take a lot of work. Yes, people do figure it out on their own I know people, I am one, who came to industry without training in teaching and did a pretty good job. Enthusiasm and great students will get you pretty far. That’s not the ideal I look back and wonder how much better my students would have been if I had known what I know about teaching CS back then. I don’t think I messed anyone up too much but could I have taken them further? I like to think so.

If CS is going to take its place with other core subjects we have to learn to teach it well. We have to have more than just enthusiasm for the subject.. We have to set high standards for teachers as well as students.

Facebook Conversations

Mike Zamansky’s post of the subject

Monday, November 16, 2020

Tiny Book of Simple Cryptography

I've been playing with simple cryptography. Mostly stuff that was solid before computers. Just for fun mostly but some of it may make for interesting projects for students. I've written a little bit about the things I have been playing with.

This is not a big book and it is intended more to spark interest and not to be a real reference book. There are footnotes linking to Wikipedia articles that would be a good next step for learning more.

I have a couple of substitution ciphers and a couple of  transposition ciphers. Added some Steganography

Comments and gentle criticism welcome. I have coded solutions in C# that are ok. Some of them even have comments.

Updated 5 March 2021 to include a brief chapter on the PigPen Cipher. Also some minor edits in other sections.