问:
How to represent a graph with multiple edges allowed between nodes and edges that can selectively disappear
I'm trying to figure out what sort of data structure to use for modeling some hypothetical, idealized network usage.

In my scenario, a number of users who are hostile to each other are all trying to form networks of computers where all potential connections are known. The computers that one user needs to connect may not be the same as the ones another user needs to connect, though; user 1 might need to connect computers A, B and D while user 2 might need to connect computers B, C and E.

Image generated with the help of NCTM Graph Creator

I think the core of this is going to be an undirected cyclic graph, with nodes representing computers and edges representing Ethernet cables. However, due to the nature of the scenario, there are a few uncommon features that rule out adjacency lists and adjacency matrices (at least, without non-trivial modifications):

edges can become restricted-use; that is, if one user acquires a given network connection, no other user may use that connection

in the example, the green user cannot possibly connect to computer A, but the red user has connected B to E despite not having a direct link between them

in some cases, a given pair of nodes will be connected by more than one edge

in the example, there are two independent cables running from D to E, so the green and blue users were both able to connect those machines directly; however, red can no longer make such a connection

if two computers are connected by more than one cable, each user may own no more than one of those cables

I'll need to do several operations on this graph, such as:

determining whether any particular pair of computers is connected for a given user

identifying the optimal path for a given user to connect target computers

identifying the highest-latency computer connection for a given user (i.e. longest path without branching)

My first thought was to simply create a collection of all of the edges, but that's terrible for searching. The best thing I can think to do now is to modify an adjacency list so that each item in the list contains not only the edge length but also its cost and current owner. Is this a sensible approach? Assuming space is not a concern, would it be reasonable to create multiple copies of the graph (one for each user) rather than a single graph?

答:
Assuming space is not a concern, would it be reasonable to create multiple copies of the graph (one for each user) rather than a single graph?

It seems to me that you should use what we could label ”layered graphs”, i.e. add a combinator for graphs, say @, so that:

If A and B are graphs then A@B is also a graph (i.e. can be fed to the algorithms of your graph library).

The set of vertices in A@B is the union of vertices in A and B.

The set of edges in A@B is the union of edges in A and B.

The structure A@B does not own any vertex or edge, but rather uses A and B as data containers.

With such layered graphs, you can define K to be the kommon available information and R, G, B each private information so that each player is actually seeing R@K, G@K, B@K.

To actually implement this, you may look for a graph library implementing algorithms generically, i.e. so that the longest path algorithm etc. are parametrised by the actual representation of your graph. So if your library says

```<code>ConcreteGraphAlgorithms = GenericAlgorithms(ConcreteGraphImplementation)
</code>```

you can easily replace it with

```<code>LayeredGraphAlgorithms = GenericAlgorithms(LayeredGraphs(ConcreteGraphImplementation))
</code>```

where you are supplying the LayeredGraphs and borrowing the rest from the library.

Body:
Assuming space is not a concern, would it be reasonable to create multiple copies of the graph (one for each user) rather than a single graph?

It seems to me that you should use what we could label ”layered graphs”, i.e. add a combinator for graphs, say @, so that:

If A and B are graphs then A@B is also a graph (i.e. can be fed to the algorithms of your graph library).

The set of vertices in A@B is the union of vertices in A and B.

The set of edges in A@B is the union of edges in A and B.

The structure A@B does not own any vertex or edge, but rather uses A and B as data containers.

With such layered graphs, you can define K to be the kommon available information and R, G, B each private information so that each player is actually seeing R@K, G@K, B@K.

To actually implement this, you may look for a graph library implementing algorithms generically, i.e. so that the longest path algorithm etc. are parametrised by the actual representation of your graph. So if your library says

ConcreteGraphAlgorithms = GenericAlgorithms(ConcreteGraphImplementation)

you can easily replace it with

LayeredGraphAlgorithms = GenericAlgorithms(LayeredGraphs(ConcreteGraphImplementation))

where you are supplying the LayeredGraphs and borrowing the rest from the library.


问:
In the days of modern computing, in 'typical business apps' - why does performance matter?
This may seem like an odd question to some of you.

I'm a hobbyist Java programmer. I have developed several games, an AI program that creates music, another program for painting, and similar stuff. This is to tell you that I have an experience in programming, but not in professional development of business applications.

I see a lot of talk on this site about performance. People often debate what would be the most efficient algorithm in C# to perform a task, or why Python is slow and Java is faster, etc.

What I'm trying to understand is: why does this matter?

There are specific areas of computing where I see why performance matters: games, where tens of thousands of computations are happening every second in a constant-update loop, or low level systems which other programs rely on, such as OSs and VMs, etc.

But for the normal, typical high-level business app, why does performance matter?

I can understand why it used to matter, decades ago. Computers were much slower and had much less memory, so you had to think carefully about these things.

But today, we have so much memory to spare and computers are so fast: does it actually matter if a particular Java algorithm is O(n^2)? Will it actually make a difference for the end users of this typical business app?

When you press a GUI button in a typical business app, and behind the scenes it invokes an O(n^2) algorithm, in these days of modern computing - do you actually feel the inefficiency?

My question is split in two:

In practice, today does performance matter in a typical normal business program?

If it does, please give me real-world examples of places in such an application, where performance and optimizations are important.

答:
I understood your question like this: in order to achieve good-enough performances (i.e. users are happy and my backend doesn't cringe), do I need to understand the theory on algorithmic complexity?

It depends on what you mean by "typical" business application. In many cases, especially simple CRUD-like information systems, the answer would be no. For these you'll "simply" (sometimes it's actually hard) need to be able to trace the performances bottlenecks: did I miss an index in my database? Do I send too much data over the network? Do I have a thousand $watch in my angular.js front-end? This is about building a sound architecture, knowing your technology stack well, and avoiding non-sense. You can achieve that if you are a good crafter, not necessarily a computer scientist. Another way to say it is that the guys who built the Oracle query optimizer dealt with the algorithmic complexity stuff, you just need to use properly what they provided to you.

Now there are exceptions. If we're talking about big data or machine learning, you need to know what you are doing and not just use the default algorithms available to you. Even on the front end, if you start building advanced data visualizations some of them can imply a non linear complexity cost (e.g. force-layout charts).

Nowadays these exception are becoming more and more common and the market is pretty dry when you look for people who can handle them. So: yes, you can be successful with no computer science background, but you'll be even more with some.

ContentLicense: CC BY-SA 3.0


答:
It certainly matters a lot.

The main issue is not even about being annoying for the user, such as experiencing needless delays when GUI elements are overdrawn twice or thrice (which does matter on integrated graphics!) or simply because the program takes so long to do... whatever it does (mostly uninteresting stuff). Although of course, that is also an issue.

There are three important misconceptions:

Most typical business computers are not "so much more powerful". The typical business computer is not a 8-core i7 with a kick-ass graphics card and 16GB of RAM. It's a notebook with a mid-class mobile processor, integrated graphics, 2GB of main memory (4GB if you are lucky), a 5400RPM disk, and an enterprise version of Windows with a variety of realtime antivirus and policy-enforcing software running in the background. Or, for most consultants, the "computer" is simply the iPhone...

Most "typical business users" are not technicians, they do not understand the implications of creating a spreadsheet with 10-12 cross-referencing tabs, 150 columns, and 30,000 rows (these figures are not as unrealistic as you may assume!) and they do not want to know either. They will just do it.

A second lost doesn't cost is a blatantly wrong assumption.

My wife works at the upper end of such a "typical business environment". The computer that she is using costs about as much as 3.5 hours of her working time are worth. Starting Microsoft Outlook takes -- on a good day -- about 3 minutes until it's ready (6-8 minutes on quarter-end when the servers are under heavy load). Some of those 30k-row-spreadsheets mentioned take 2-3 seconds for updating a value during which the computer is "frozen" (not to mention how long it takes Excel to start up and open them in the first place!). It's even worse when sharing desktop. Don't even get me going on SAP.

It certainly matters whether a hundred thousand people each lose 20-25 minutes per working day waiting for nothing. Those are millions lost which you could, instead of losing them, pay out as dividends (or pay higher wages).

Sure, most of the employees are on the lower end of the payscale, but even on the lower end time is money.

Title: In the days of modern computing, in 'typical business apps' - why does performance matter?

Body:
This may seem like an odd question to some of you.

I'm a hobbyist Java programmer. I have developed several games, an AI program that creates music, another program for painting, and similar stuff. This is to tell you that I have an experience in programming, but not in professional development of business applications.

I see a lot of talk on this site about performance. People often debate what would be the most efficient algorithm in C# to perform a task, or why Python is slow and Java is faster, etc.

What I'm trying to understand is: why does this matter?

There are specific areas of computing where I see why performance matters: games, where tens of thousands of computations are happening every second in a constant-update loop, or low level systems which other programs rely on, such as OSs and VMs, etc.

But for the normal, typical high-level business app, why does performance matter?

I can understand why it used to matter, decades ago. Computers were much slower and had much less memory, so you had to think carefully about these things.

But today, we have so much memory to spare and computers are so fast: does it actually matter if a particular Java algorithm is O(n^2)? Will it actually make a difference for the end users of this typical business app?

When you press a GUI button in a typical business app, and behind the scenes it invokes an O(n^2) algorithm, in these days of modern computing - do you actually feel the inefficiency?

My question is split in two:

In practice, today does performance matter in a typical normal business program?

If it does, please give me real-world examples of places in such an application, where performance and optimizations are important.


答:
I can understand why it used to matter, decades ago. Computers were
  much slower and had much less memory, so you had to think carefully
  about these things.

You seem to underestimate just how quickly N^2 grows.  Lets say we have a computer and our N^2 algorithm takes 10 seconds when N = 10.  Time passes we now have a new processor that is 6 times faster than our original so our 10 second computation is now less than two seconds.  How much larger can N be and still fit in that original 10 second run time? We can now handle 24 items, a little over twice as much.  How much faster would our system have to be to handle 10 times as many items? Well it would have to be 100 times faster.  Data grows pretty fast and more than wipes out computer hardware progress for N^2 algorithms.


答: The other responders have covered most of the basic points, but for tasks which can be parallelized, inefficient software leads to increased hardware costs in the form of more servers, which use more power and require more space and maintenance.</p>


问:
API Class with intensive network requests
I'm working an API which works as "intermediary" between a REST API and the developer.

In this way, when the programmer do something like this:

```<code>User user = client.getUser(nickname);
</code>```

it will execute a network request to download from the service the data about the user and then the programmer can use the data by doing things like

```<code>user.getLocation();
user.getDisplayName();
</code>```

and so on.

Now there are some methods like getFollowers() which execute another network request and i could do it in two ways:

Download all the data in the getUser method (and not only the most important) but in this way the request time could be very long since it should execute the request to various urls

Download the data when the user calls the method, it looks like the best way and to improve it i could cache the result so the next call to getFollowers returns immediately with the data already download instead of execute again the request.

What is the best way? And i should let methods like getUser and getFollowers stop the code execution until the data is ready or i should implement a callback so when the data is ready the callback gets fired? (this looks like Javascript)

答:
It is more convenient for you if you grab all the relevant data (about the user, the followers, etc.) in just one routine. You don't have to worry about the partitioning of the access among several calls, or having some information available and some not, etc.

But having one big, honking call that takes a (possibly) long time to execute, and consumes a lot of both local and remote server resources to boot--that is a low scalability, anti-social design. I'm not saying never, ever do that--but it's a lot more appropriate in exploratory prototypes than production code.

If you wish your User object to mask interactions with the REST API, then your getFollowers method should invoke the required behind-the-scenes shuffle to grab the followers information, then cache it locally. That is completely appropriate and typical. While the first request will take much longer than subsequent requests, c'est la vie.

Unless you are in a highly performance-constrained or latency-sensitive situation, it is unlikely that you want to involve asynchronous request/return mechanisms. They are complicated to get right, and notably complicate both your logic and that of User consumers.

You see async calls often in JavaScript--along with an army of callback handlers, registered event handlers, promises, futures, and other rendezvous techniques. That's because JS has no other good mechanisms for handling threading/concurrency, and async has become the language idiom. You can do async calls in Java, for example with Futures. But by and large, Java programs tend to favor threads over async calls, and Java API consumers predominantly expect synchronous methods. Unless you have a specific requirement to do things async, or believe doing so will yield a substantial performance/latency win, don't. Don't do things that require your consumers to adopt an unexpected model of concurrency.

Note also that many REST APIs are paged. Requests like "get followers" or "get posts" return the first 20, 50, or whatever. Getting the next N objects requires a subsequent call. In those cases, making network / REST APIs calls is something that your getter methods might have to do across the life of your User objects, not just once or twice "up front."


答:
Many of the other answers cover the topic quite thoroughly, so I defer to them on the reasons and rationales. Instead, I want to give a real-life example to show how an algorithmic choice can have real implications.

http://windowsitpro.com/windows-xp/svchost-and-windows-update-windows-xp-still-problem

The linked article describes a bug in the algorithm to calculate Windows XP updates. For most of the life of Windows XP, the update algorithm worked fine. The algorithm calculates whether a patch has been superseded by a newer patch, and thus does not need installed. Towards the end, though, the list of superseded updates grew very long*.

The update algorithm was exponential, where each new update took twice as long to calculate as the previous one (O(n) = 2n). When the lists got up into the 40 updates range (*long), it took up to 15 minutes, running at full capacity, to check for updates. This effectively locked up many XP machines during the update. Worse yet, when one would go to install the updates, the algorithm would run again, taking another 15 minutes. Since many machines had Automatic Updates set, this could lock up the machines for 15 minutes at every boot, and potentially again at a certain periodicity.

Microsoft used both short-term hacks (removing items from the update list) and long-term fixes to address this issue. This was important because the latest versions of Windows were also using the same algorithm, and might one day face the same problem.

Here we can see that the choice of an algorithm had real implications. The wrong algorithm, while fine for most of the life of the product, can still have negative impacts down the road.


答:
It depends heavily on how you define "good performance". Your algorithms should always use the best possible complexity. Abuse loopholes to speed up your average cage. Buffer and preload/precompile wherever possible in an interactive program.

There is another definition of "good performance": Optimizing the constants of your complexity class. This is where C++ gets his title, where people start to call Java slow, where 5% less runtime seems to be the holy grail.
Using this definition you're right. Computer hardware gets more complicated with time, while compilers get better and better. At some point you can't really optimize low end code better than the compiler - so just let it be and concentrate on your algorithms.

At that point using Java / Haskell / C++ becomes just another design decision. Number crunching can be done via OpenCL on your GPU. User Interfaces need constant time algorithms and they're good. Output and modularity is more important than aligning your classes for 20% better cache utilization. Multithreading becomes important, because people don't want a fast app, they want a responsive one. What is not important is your app being constantly 10% slower than it could be. Even 50% is fine (but people start asking questions then). Concentrate on correctness, responsiveness and modularity.

I love programming in Haskell or at least in a functional form (even in C++). Being able to write tests easily for your entire program is just way more important than being a little faster in batch jobs.


答:
Quite simple: cost

My previous employer had a learning management system that was hosted on physical servers as a SaaS model.  The JVM's heap was configured to 2 GB for the older machines and 3 GB for the newer machines and we ran several instances per machine.  You'd think that would be enough.

Before I started, there was a performance team responsible for making the system responsive and scale.  They found that there were certain pieces of data that we queried from the database constantly.  There was one table we even joined in to most queries to retrieve one column.  That data rarely changed.

The trouble is, we had 2 GB to work with.  So the obvious solution is to start caching all of the frequently read data.  Then we had memory issues, starting right before I came on board.

There were 2 schools of thought on this:

Memory and hardware in general is cheap these days.  Just buy more RAM so you can cache more.

Why does a learning management system need 3+ GB of RAM?  All it does it issue SQL queries, send redirects to launch courses, and evaluate students' progress through courses.

The second argument won out and I spent over a year tuning our memory usage.

My current employer also hosts a learning manage system, but hosts it a bit differently.  The scalability is so poor that a single installation (split across 4 load balanced virtual servers) can only handle 80 customers.  Some of our larger customers even get their own set of servers.  Most of the issues leading to this are performance problems, like SQL queries which hog all of the CPU cycles, memory leaks, redundant code that does the same thing multiple times.  We even have an in-house app built whose sole purpose is to restart servers when they are not performing poorly.  There is an employee who maintains that tool (along with other responsibilities).

They subscribed to the first school of thought I mentioned above: throw more hardware at it because hardware costs are cheaper than developer salaries.

This did not work out as economically as expected.  Between hardware, software licensing, and support personnel to handle the servers, we spent millions every year to avoid having a developer spend time profiling code.

When I joined, I was made responsible for fixing our availability issues.  Since most of our availability issues were due to poor performance, I have been performance tuning our code and the scalability is substantially improved, with much better uptime.  We are ready to start increasing the density.  Needless to say, my salary is nowhere near a million (I wish!), so spending money on having me performance tune the code is going to end up saving us millions per year.

TL;DR

If you do a thorough cost/benefit analysis, you will see that it is cheaper to just fix the code.  A known performance issue that you ignore turns into technical debt.


问:
How to handle "circular dependency" in dependency injection
The title says "Circular Dependency", but it is not the correct wording, because to me the design seems solid.

However, consider the following scenario, where the blue parts are given from external partner, and orange is my own implementation. Also assume there is more then one ConcreteMain, but I want to use a specific one. (In reality, each class has some more dependencies, but I tried to simplify it here)

I would like to instanciate all of this with Depency Injection (Unity), but I obviously get a StackOverflowException on the following code, because Runner tries to instantiate ConcreteMain, and ConcreteMain needs a Runner.

```<code>IUnityContainer ioc = new UnityContainer();
ioc.RegisterType<IMain, ConcreteMain>()
   .RegisterType<IMainCallback, Runner>();
var runner = ioc.Resolve<Runner>();
</code>```

How can I avouid this? Is there any way to structure this so that I can use it with DI? The scenario I'm doing now is setting everything up manually, but that puts a hard dependency on ConcreteMain in the class which instantiates it. This is what i'm trying to avoid (with Unity registrations in configuration).

All source code below (very simplified example!);

```<code>public class Program
{
    public static void Main(string[] args)
    {
        IUnityContainer ioc = new UnityContainer();
        ioc.RegisterType<IMain, ConcreteMain>()
           .RegisterType<IMainCallback, Runner>();
        var runner = ioc.Resolve<Runner>();

        Console.WriteLine("invoking runner...");
        runner.DoSomethingAwesome();

        Console.ReadLine();
    }
}

public class Runner : IMainCallback
{
    private readonly IMain mainServer;

    public Runner(IMain mainServer)
    {
        this.mainServer = mainServer;
    }

    public void DoSomethingAwesome()
    {
        Console.WriteLine("trying to do something awesome");
        mainServer.DoSomething();
    }

    public void SomethingIsDone(object something)
    {
        Console.WriteLine("hey look, something is finally done.");
    }
}

public interface IMain
{
    void DoSomething();
}

public interface IMainCallback
{
    void SomethingIsDone(object something);
}

public abstract class AbstractMain : IMain
{
    protected readonly IMainCallback callback;

    protected AbstractMain(IMainCallback callback)
    {
        this.callback = callback;
    }

    public abstract void DoSomething();
}

public class ConcreteMain : AbstractMain
{
    public ConcreteMain(IMainCallback callback) : base(callback){}

    public override void DoSomething()
    {
        Console.WriteLine("starting to do something...");
        var task = Task.Factory.StartNew(() =>{ Thread.Sleep(5000);/*very long running task*/ });
        task.ContinueWith(t => callback.SomethingIsDone(true));
    }
}
</code>```

答:
What you can do is to create a factory, MainFactory that returns an instance of ConcreteMain as IMain.

Then you can inject this Factory into your Runner constructor.
Create the Main with the factory and pass inn itself as a parameter.

Any other dependencies on the ConcreteMain constructor can be passed into the MyMainFactory via IOC and pushed to the concrete constructor manually.

```<code>public class MyMainFactory
{
    MyOtherDependency _dependency;

    public MyMainFactory(MyOtherDependency dependency)
    {
        _dependency = dependency;
    }

    public IMain Create(Runner runner)
    {
        return new ConcreteMain(runner, _dependency);
    }
}

public class Runner
{
    IMain _myMain;
    public Runner(MyMainFactory factory)
    {
        _myMain = factory.Create(this)
    }
}
</code>```

Body:
What you can do is to create a factory, MainFactory that returns an instance of ConcreteMain as IMain.

Then you can inject this Factory into your Runner constructor.
Create the Main with the factory and pass inn itself as a parameter.

Any other dependencies on the ConcreteMain constructor can be passed into the MyMainFactory via IOC and pushed to the concrete constructor manually.

public class MyMainFactory
{
    MyOtherDependency _dependency;

    public MyMainFactory(MyOtherDependency dependency)
    {
        _dependency = dependency;
    }

    public IMain Create(Runner runner)
    {
        return new ConcreteMain(runner, _dependency);
    }
}

public class Runner
{
    IMain _myMain;
    public Runner(MyMainFactory factory)
    {
        _myMain = factory.Create(this)
    }
}


问:
Is goto to improve DRY-ness OK?
My code has many checks to detect errors in various cases (many conditions would result in the same error), inside a function returning an error struct. Instead of looking like this:

```<code>err_struct myfunc(...) {
    err_struct error = { .error = false };

    ...

    if(something) {
        error.error = true;
        error.description = "invalid input";
        return error;
    }

    ...

        case 1024:
            error.error = true;
            error.description = "invalid input";  // same error, but different detection scenario
            return error;
            break;  // don't comment on this break please (EDIT: pun unintended)
            ...
</code>```

Is use of goto in the following context considered better than the previous example?

```<code>err_struct myfunc(...) {
    err_struct error = { .error = false };

    ...

    if(something) goto invalid_input;

    ...

        case 1024:
            goto invalid_input;
            break;

    return error;

    invalid_input:
        error.error = true;
        error.description = "invalid input";
        return error;
</code>```

答:
When you see a good move, look for a better one.

    —Emanuel Lasker, 27-year world chess champion

Cleanup/error handling of that form is one of the acceptable uses of goto, especially in C.  Using a goto is better than repeating those three lines, but you can do better still.  Always look for the better move.

For one thing, it's unlikely those errors are truly identical.  At some point, someone is going to wonder which condition you've actually hit, then you're back where you started.  You need a succinct way to distinguish between different errors at the point they are detected.

Here's one solution:

```<code>const err_struct myfunc(...) {
    const err_struct success       = { .error = false };
    const err_struct invalid_input = { .error = true, .description = "invalid input" };

    ...

    if(something)
        return invalid_input;

    ...

        case 1000:
            return custom_error("Expected %d, found 1000", expected);

        case 1024:
            return invalid_input;

    ...

    return success;
}
</code>```

For commonly-used error descriptions, I would define them together with err_struct, which would make it easier to be consistent with wording throughout your system, and helps keep an accidental typo in a description from breaking your code.

Title: Is goto to improve DRY-ness OK?

Body:
When you see a good move, look for a better one.

    —Emanuel Lasker, 27-year world chess champion

Cleanup/error handling of that form is one of the acceptable uses of goto, especially in C.  Using a goto is better than repeating those three lines, but you can do better still.  Always look for the better move.

For one thing, it's unlikely those errors are truly identical.  At some point, someone is going to wonder which condition you've actually hit, then you're back where you started.  You need a succinct way to distinguish between different errors at the point they are detected.

Here's one solution:

const err_struct myfunc(...) {
    const err_struct success       = { .error = false };
    const err_struct invalid_input = { .error = true, .description = "invalid input" };

    ...

    if(something)
        return invalid_input;

    ...

        case 1000:
            return custom_error("Expected %d, found 1000", expected);

        case 1024:
            return invalid_input;

    ...

    return success;
}

For commonly-used error descriptions, I would define them together with err_struct, which would make it easier to be consistent with wording throughout your system, and helps keep an accidental typo in a description from breaking your code.


问:
Changelog Management
I'm currently developing a WinForm application.
In order to inform the client about the improvements and corrections made during the last version, I would like to manage and display a changelog.

I mostly found existing changelog on website (the term changelog is pretty used) or explanation on how to manage the release numbers, which I don't care.

So, these are my questions:

How do I manage a changelog (using XML, pure text in the app, etc.) in a desktop application?

How do I present it to the user (external website, inside the winform application)?

答:
This is primarily a user interface question.  Therefore: (1) You might want to check ux.stackexchange.com. (2) The correct answer to most, "What's the best UI?" questions is, "Do a test (such as a hallway usability test) and find out for yourself."

With that out of the way...

"Informing the client about the improvements and corrections made during the last version" can take a few different forms:

"What's New", presented as end-user documentation (not programmer's perspective ocumentation) on things the user needs to know to help them better use the software.

"What's New", presented as more of a marketing document, giving a list of reasons to upgrade or renew or whatever

A changelog - a detailed list of every potentially user-visible change, commonly one change per line

It sounds like you're interested in a changelog, but don't neglect "What's New" documentation either.

How to manage your changelog? However you want to, really. Users won't care about the format, so do whatever format's easiest for you: auto-generated text from Git's short messages, XML, HTML, Markdown that you convert to HTML, whatever. I personally like HTML (or Markdown to HTML), because it's easy to work with and can be displayed by a variety of tools.

How to display it? Whatever presents a good UI and is easiest. I like a web browser, since the browser's UI probably gets a lot more attention than you can devote to your WinForms app, and if you host the changelog on your website and point customers to it, you can use analytics, fix typos, etc.

Whatever you do, keep in mind that, as David Platt writes, "Users don’t care about your program in and of itself." A detailed one-change-per-line changelog is likely of interest to very few users, and trying to get them to read one if all they want to do is fire up the app and get work done will likely do no good. A "What's New" guided tour or tip of the day, as long as it's not obnoxious and can be easily deferred until the customer wants to take the time to go through it, takes more work to implement but should produce better results.

Title: Changelog Management


答:
To me the best solution seems to be a method that takes an optional parameter that allows the caller to determine whether or not to include the follower data.  In this way the caller can determine if it is appropriate to include the follower data in the call.

In a worst case scenario you have a few extra lines of code that never matter because the call always wants all of the data.  However if the caller does not need all of that data and the application sees some performance hits from the collection of the extra data then some fine tuning can be done to allow for the conditional loading of the follower data.

On the other hand if you hard code it to always get the follower data then if it does become a performance issue the change will be more work if you have to make the change to allow for it at the call, or to make a separate call that only gets the user information.  Implementing the optional parameter now should be a trivial task, and allow for the best fine tuning of the application with out having to modify your API.

Title: API Class with intensive network requests

Body:
I'm working an API which works as "intermediary" between a REST API and the developer.

In this way, when the programmer do something like this:

```<code>User user = client.getUser(nickname);
</code>```

it will execute a network request to download from the service the data about the user and then the programmer can use the data by doing things like

```<code>user.getLocation();
user.getDisplayName();
</code>```

and so on.

Now there are some methods like getFollowers() which execute another network request and i could do it in two ways:

Download all the data in the getUser method (and not only the most important) but in this way the request time could be very long since it should execute the request to various urls

Download the data when the user calls the method, it looks like the best way and to improve it i could cache the result so the next call to getFollowers returns immediately with the data already download instead of execute again the request.

What is the best way? And i should let methods like getUser and getFollowers stop the code execution until the data is ready or i should implement a callback so when the data is ready the callback gets fired? (this looks like Javascript)


问:
Should we enforce code style in our large codebase?
By "code style" I mean 2 things:

Style, eg.

```<code>// bad
if(foo){ ... }

// good
if (foo) { ... }
</code>```

Conventions and idiomaticity, where two ways of writing the same thing are functionally equivalent, but one is more idiomatic. eg.

```<code>// bad
if (fooLib.equals(a, b)) { ... }

// good
if (a == b) { ... }
</code>```

I think it makes sense to use an auto-formatter to enforce #1 automatically. So my question is specifically about #2. I like to break things down into pros and cons, here's what I've come up with so far:

Pros:

Used by many large codebases (eg. Google, jQuery)

Helps make it a bit easier to work on new areas of the codebase

Helps make code more portable (this is not necessarily true)

Code style is automatic once you get used to it

Makes it easier to fast-decline pull requests

Cons:

Takes engineers’ and code reviewers’ time away from more important things (like developing features)

Code should ideally be rewritten every 2-3 years anyway, so it’s more important to focus on getting the architecture right, and achieving high test coverage

Adds strain to code reviews (eg. “don’t do it this way, I like this other way better”)

Even if I’ve been using a code style for a while, I still sometime have to pause and think about how to write a line better

Having an enforced, uniform code style makes it hard to experiment with potentially better styles

Maintaining a style guide takes a lot of incremental effort

Engineers rarely read through the style guide. More often, it's cited in code reviews

And as a secondary question: we also have many smaller repositories - should the same code style be enforced there?

答:
Use a linter or some program or tool that automatically enforces style.  That should alleviate the objections about it taking too much time.

Most of the objections have to do with "I'm uncomfortable with that style."  It doesn't matter.  Coding conventions are all about uniformity.  Enforcing that uniformity will make code reviews easier by eliminating discussions about that, and allowing code reviews to focus on more substantial issues.


问:
single for-loop runtime explanation problem
I am analyzing some running times of different for-loops, and as I'm getting more knowledge, I'm curious to understand this problem which I have still yet to find out.
I have this exercise called "How many stars are printed":

```<code>for (int i = N; i > 1; i = i/2) System.out.println("*");
</code>```

The answers to pick from is

A: ~log N
B: ~N
C: ~N log N
D: ~0.5N^2

So the answer should be A and I agree to that, but on the other side.. Let's say N = 500 what would Log N then be? It would be 2.7. So what if we say that N=500 on our exercise above? That would most definitely print more han 2.7 stars? How is that related?

Because it makes sense to say that if the for-loop looked like this:

```<code>for (int i = 0; i < N; i++)
</code>```

it would print N stars.

I hope to find an explanation for this here, maybe I'm interpreting all these things wrong and thinking about it in a bad way. Thanks in advance.

答: In addition to Michael Borgwardt's answer, the tilde character in front of each answer should be read as "proportional to". So if you doubled N (say, from 500 to 1000), you would see that the run time (or, in this case, number of stars printed) would increase by a factor which would be equal to (log1000 / log 500), which is independent from which base you use.</p>


答:
I think the code style works the other way -- it helps reviewer understand the code easier, save their time, and helps maintenance in the future.

Also, reviewers shouldn't force others to use a code style, but they should point things out if that gonna cause some trouble (especially seniors).

Automatic style tool should be ok but also should be optional -- as some developer might not like to style their code for some reasons.

Title: Should we enforce code style in our large codebase?

Body:
By "code style" I mean 2 things:

Style, eg.

```<code>// bad
if(foo){ ... }

// good
if (foo) { ... }
</code>```

Conventions and idiomaticity, where two ways of writing the same thing are functionally equivalent, but one is more idiomatic. eg.

```<code>// bad
if (fooLib.equals(a, b)) { ... }

// good
if (a == b) { ... }
</code>```

I think it makes sense to use an auto-formatter to enforce #1 automatically. So my question is specifically about #2. I like to break things down into pros and cons, here's what I've come up with so far:

Pros:

Used by many large codebases (eg. Google, jQuery)

Helps make it a bit easier to work on new areas of the codebase

Helps make code more portable (this is not necessarily true)

Code style is automatic once you get used to it

Makes it easier to fast-decline pull requests

Cons:

Takes engineers’ and code reviewers’ time away from more important things (like developing features)

Code should ideally be rewritten every 2-3 years anyway, so it’s more important to focus on getting the architecture right, and achieving high test coverage

Adds strain to code reviews (eg. “don’t do it this way, I like this other way better”)

Even if I’ve been using a code style for a while, I still sometime have to pause and think about how to write a line better

Having an enforced, uniform code style makes it hard to experiment with potentially better styles

Maintaining a style guide takes a lot of incremental effort

Engineers rarely read through the style guide. More often, it's cited in code reviews

And as a secondary question: we also have many smaller repositories - should the same code style be enforced there?


答:
The point is that you need to use an automated tool which enforces style on every commit. The applies to both examples from your question. In .NET, the first piece of code will be enforced by StyleCop, while the second one—by Code analysis (for inspiration, see CA1820).

The goal of having a style guide is to:

Enforce uniform style in order to make the code base easier to read and maintain by reducing the effort required by a different style than the one the reader usually uses. Example: tabs vs. spaces.

Discourage situations where bugs are introduced more easily. For example, by forbidding to end the line of code by whitespace, you may mitigate the risk of introducing some bugs which are moreover difficult to pinpoint:

```<code>#!/bin/bash
cp·-r·/hello/world·\·     ← This space at the end is annoying.
      /demo/destination/
</code>```

In both cases, rules can and should be automated.

Once you use an automated tool, the cons from your question become irrelevant.

Takes engineers’ and code reviewers’ time away from more important things (like developing features)

If you use automatic style checker, correcting those errors at the beginning can waste some time to the authors, but with practice, it will quickly become a very easy task which takes in worst cases a few minutes.

Code should ideally be rewritten every 2-3 years anyway, so it’s more important to focus on getting the architecture right, and achieving high test coverage

There is nothing to "focus" on. You write code, you commit it, if there is a style error, you correct it and commit again. And you do that while keeping all your focus on the readability of the code, maintainability, architecture, design and reliability/testing.

Also, why do you have to rewrite code every 2-3 years? Shouldn't you be concerned by the quality of the code which requires such time-costly rewriting?

Adds strain to code reviews (eg. “don’t do it this way, I like this other way better”)

You shouldn't mention nor discuss style during code reviews.

Even if I’ve been using a code style for a while, I still sometime have to pause and think about how to write a line better

Better as opposed to compliant to the style guide? In four years using StyleCop and a few months using PEP 8, I never found myself in a situation where adopting a non-uniform style would substantially improve the readability.

Having an enforced, uniform code style makes it hard to experiment with potentially better styles

Which doesn't matter. Frankly, there is no right answer to whether you should use tabs or spaces or whether you should put { on a new line. There is nothing to experiment with. Most rules are somehow arbitrary: what counts is not which rule was chosen, but the fact that the rule was chosen and is now enforced, making the code base consistent.

Note that you shouldn't follow style rules religiously, without understanding why are they written in their current form. Some rules (tabs vs. spaces) really don't have a convincing explanation. Others have an interesting reasoning. For example, this piece of code:

```<code>var demo = [
    someElementHere,
    anotherOne,
    helloWorld,
    goodBye,
];
</code>```

is better than:

```<code>var demo = [
    someElementHere,
    anotherOne,
    helloWorld,
    goodBye       ← Noticed the lack of comma?
];
</code>```

Why? Because in the first case, if you add a new element to the array and commit, the commit consists of one new line. In the second piece of code, the commit will consist of one new line and one modified line. The first one is semantically more correct in a diff.

Another interesting example is code used to advertise jsHint as being better than Douglas Crockford's jsLint. The code contains a mistake which is not obvious to see by a beginner. jsLint catches this mistake and displays a error. jsHint doesn't catch it, letting you to find it yourself when one day, in production, the web app starts behaving unexpectedly.

Maintaining a style guide takes a lot of incremental effort

Don't reinvent the wheel. Most languages already have a style guide. A benefit of using an existent one is that most newcomers will already know it, whereas nobody will know yours.

Engineers rarely read through the style guide. More often, it's cited in code reviews

That's why it should be enforced during commits.

Now your main question:

Should we enforce code style in our large codebase?

Ask your team. Is code style inconsistency an issue for your team? Are at least some members constantly complaining about the style of their pairs? Do you have commits which intentionally change style, and only style? Do you have unreadable diffs because someone decided to replace all tabs by spaces or add spaces before and after each parenthesis?

If yes, you have to enforce code style. Otherwise, the team members are wasting their time.

Note that this task is not easy. You want to avoid discussions about which style is better at all costs: otherwise, you'll find yourself making compromises, and finally, you'll end up with no style enforcement at all.

If you're interested in the difficulties of introducing a style into an existent code base, ask a separate question, and I'll be happy answering it in more detail.

If not, don't bring the subject. Team members are happy with the current inconsistency, or at least they learnt to deal with it. Many developers are in this case: often, ones who switched jobs a lot or who used a lot of different programming languages can't care less and are able to read and understand code with any style.

Enforcing style in this case would only slow things down. The team would be forced to walk through the entire code base. The bigger is the code base, the harder is to fix the style. If the code is not tested enough, there is also a risk of introducing regressions.

Body:
The point is that you need to use an automated tool which enforces style on every commit. The applies to both examples from your question. In .NET, the first piece of code will be enforced by StyleCop, while the second one—by Code analysis (for inspiration, see CA1820).

The goal of having a style guide is to:

Enforce uniform style in order to make the code base easier to read and maintain by reducing the effort required by a different style than the one the reader usually uses. Example: tabs vs. spaces.

Discourage situations where bugs are introduced more easily. For example, by forbidding to end the line of code by whitespace, you may mitigate the risk of introducing some bugs which are moreover difficult to pinpoint:

#!/bin/bash
cp·-r·/hello/world·\·     ← This space at the end is annoying.
      /demo/destination/

In both cases, rules can and should be automated.

Once you use an automated tool, the cons from your question become irrelevant.

Takes engineers’ and code reviewers’ time away from more important things (like developing features)

If you use automatic style checker, correcting those errors at the beginning can waste some time to the authors, but with practice, it will quickly become a very easy task which takes in worst cases a few minutes.

Code should ideally be rewritten every 2-3 years anyway, so it’s more important to focus on getting the architecture right, and achieving high test coverage

There is nothing to "focus" on. You write code, you commit it, if there is a style error, you correct it and commit again. And you do that while keeping all your focus on the readability of the code, maintainability, architecture, design and reliability/testing.

Also, why do you have to rewrite code every 2-3 years? Shouldn't you be concerned by the quality of the code which requires such time-costly rewriting?

Adds strain to code reviews (eg. “don’t do it this way, I like this other way better”)

You shouldn't mention nor discuss style during code reviews.

Even if I’ve been using a code style for a while, I still sometime have to pause and think about how to write a line better

Better as opposed to compliant to the style guide? In four years using StyleCop and a few months using PEP 8, I never found myself in a situation where adopting a non-uniform style would substantially improve the readability.

Having an enforced, uniform code style makes it hard to experiment with potentially better styles

Which doesn't matter. Frankly, there is no right answer to whether you should use tabs or spaces or whether you should put { on a new line. There is nothing to experiment with. Most rules are somehow arbitrary: what counts is not which rule was chosen, but the fact that the rule was chosen and is now enforced, making the code base consistent.

Note that you shouldn't follow style rules religiously, without understanding why are they written in their current form. Some rules (tabs vs. spaces) really don't have a convincing explanation. Others have an interesting reasoning. For example, this piece of code:

var demo = [
    someElementHere,
    anotherOne,
    helloWorld,
    goodBye,
];

is better than:

var demo = [
    someElementHere,
    anotherOne,
    helloWorld,
    goodBye       ← Noticed the lack of comma?
];

Why? Because in the first case, if you add a new element to the array and commit, the commit consists of one new line. In the second piece of code, the commit will consist of one new line and one modified line. The first one is semantically more correct in a diff.

Another interesting example is code used to advertise jsHint as being better than Douglas Crockford's jsLint. The code contains a mistake which is not obvious to see by a beginner. jsLint catches this mistake and displays a error. jsHint doesn't catch it, letting you to find it yourself when one day, in production, the web app starts behaving unexpectedly.

Maintaining a style guide takes a lot of incremental effort

Don't reinvent the wheel. Most languages already have a style guide. A benefit of using an existent one is that most newcomers will already know it, whereas nobody will know yours.

Engineers rarely read through the style guide. More often, it's cited in code reviews

That's why it should be enforced during commits.

Now your main question:

Should we enforce code style in our large codebase?

Ask your team. Is code style inconsistency an issue for your team? Are at least some members constantly complaining about the style of their pairs? Do you have commits which intentionally change style, and only style? Do you have unreadable diffs because someone decided to replace all tabs by spaces or add spaces before and after each parenthesis?

If yes, you have to enforce code style. Otherwise, the team members are wasting their time.

Note that this task is not easy. You want to avoid discussions about which style is better at all costs: otherwise, you'll find yourself making compromises, and finally, you'll end up with no style enforcement at all.

If you're interested in the difficulties of introducing a style into an existent code base, ask a separate question, and I'll be happy answering it in more detail.

If not, don't bring the subject. Team members are happy with the current inconsistency, or at least they learnt to deal with it. Many developers are in this case: often, ones who switched jobs a lot or who used a lot of different programming languages can't care less and are able to read and understand code with any style.

Enforcing style in this case would only slow things down. The team would be forced to walk through the entire code base. The bigger is the code base, the harder is to fix the style. If the code is not tested enough, there is also a risk of introducing regressions.


问:
Is there a way to avoid type-checking in this scenario?
I have a class SuperClass with two subclasses SubClassA and SubClassB. I have a method in a different class which takes a SuperClass parameter.

The method should do different things depending on the type of the object it receives. To illustrate:

```<code>public void doStuff(SuperClass object){
    // if the object is of type SubClassA, do something.
    // if it's of type SubClassB, do something else.
}
</code>```

I want to avoid type-checking (i.e. instanceof) because it doesn't feel like proper OO design.

But I can't figure out how to employ Polymorphism to elegantly solve this problem.

How can I solve this problem elegantly?

答:
The problem here is that either doStuff or SuperClass (or both) is too general to accurately describe what should be done in this action (method). The only reason you would need to check the types here is that they are poorly designed to begin with and don't offer enough of a contract to take that action.

Since you don't say what doStuff or SuperClass is actually referring to, let's say it's log(LogEventBase logEvent). Looking at this method signature, there are gaps of information that need to be filled.

What is actually being written to the log from the logEvent?

Where are we logging to?

What does it mean to be a LogMessageBase?

There are a number of other potential unanswered questions here, but you might think the solution is to base the method on the actual Type of LogEventBase:

```<code>public void log(LogMessageBase logEvent)
{
    switch (logEvent.GetType()):
        case BusinessLogicLogEvent:
            logToUserInterface(logEvent);
        case ErrorLogEvent:
            logToErrorLogs(logEvent);
        ...
</code>```

This is bad!

If it was properly designed, the answer to those questions would be written into the Types/methods directly in a number of different ways. An example of one of those ways is with a better defined interface:

```<code>public ILogMessage
{
    public GUID Id;
    public LogLevel Level;
    public string Message;
}

public void log(ILogMessage message)
{
    switch (message.LogLevel):
        case LogLevel.Error:
            logToFile(...

// or

public void logToConsole(ILogMessage message)
{
    Console.WriteLine(string.format("Message: {0}. Id: {1}",
        message.Message,
        message.Id);
}
</code>```

The point being that the Interface describes a contract for what it means to be an ILogMessage, not the Type, which could quickly grow and become unmaintainable.

There isn't a canned answer for your particular problem without knowing the data types involved. In fact, putting LogLevel directly on the ILogMessage interface could be completely wrong for your use case. I certainly don't mean to imply that you should specify an Interface that has a TypeName property and shift the responsibility there. That particular solution was only there to illustrate an example of fixing the problem (that LogMessageBase was too broad of an argument for this method) at the source so you don't need to switch on type to begin with.

Body:
The problem here is that either doStuff or SuperClass (or both) is too general to accurately describe what should be done in this action (method). The only reason you would need to check the types here is that they are poorly designed to begin with and don't offer enough of a contract to take that action.

Since you don't say what doStuff or SuperClass is actually referring to, let's say it's log(LogEventBase logEvent). Looking at this method signature, there are gaps of information that need to be filled.

What is actually being written to the log from the logEvent?

Where are we logging to?

What does it mean to be a LogMessageBase?

There are a number of other potential unanswered questions here, but you might think the solution is to base the method on the actual Type of LogEventBase:

public void log(LogMessageBase logEvent)
{
    switch (logEvent.GetType()):
        case BusinessLogicLogEvent:
            logToUserInterface(logEvent);
        case ErrorLogEvent:
            logToErrorLogs(logEvent);
        ...

This is bad!

If it was properly designed, the answer to those questions would be written into the Types/methods directly in a number of different ways. An example of one of those ways is with a better defined interface:

public ILogMessage
{
    public GUID Id;
    public LogLevel Level;
    public string Message;
}

public void log(ILogMessage message)
{
    switch (message.LogLevel):
        case LogLevel.Error:
            logToFile(...

// or

public void logToConsole(ILogMessage message)
{
    Console.WriteLine(string.format("Message: {0}. Id: {1}",
        message.Message,
        message.Id);
}

The point being that the Interface describes a contract for what it means to be an ILogMessage, not the Type, which could quickly grow and become unmaintainable.

There isn't a canned answer for your particular problem without knowing the data types involved. In fact, putting LogLevel directly on the ILogMessage interface could be completely wrong for your use case. I certainly don't mean to imply that you should specify an Interface that has a TypeName property and shift the responsibility there. That particular solution was only there to illustrate an example of fixing the problem (that LogMessageBase was too broad of an argument for this method) at the source so you don't need to switch on type to begin with.


答:
Basically, doStuff should belong to SuperClass instead of your other class, then SubClassA and SubClassB each have their own implementations.  Sometimes you might be able to pull only a small part of doStuff into SuperClass.  You might need to make OtherClass an argument of doStuff.

It's hard to say more without more details.  The bottom line is you need to try moving functionality to different classes until you find an arrangement that isn't so awkward.

Title: Is there a way to avoid type-checking in this scenario?

Body:
I have a class SuperClass with two subclasses SubClassA and SubClassB. I have a method in a different class which takes a SuperClass parameter.

The method should do different things depending on the type of the object it receives. To illustrate:

```<code>public void doStuff(SuperClass object){
    // if the object is of type SubClassA, do something.
    // if it's of type SubClassB, do something else.
}
</code>```

I want to avoid type-checking (i.e. instanceof) because it doesn't feel like proper OO design.

But I can't figure out how to employ Polymorphism to elegantly solve this problem.

How can I solve this problem elegantly?


问:
Billing from card directly
I, for the life of me, cannot find any literature on this, simply because I have no clue how it is called.

I want to learn how to implement a payment option that consists of paying with your credit/debit card directly without the use of a third party like paypal.

This is what I am talking about

Can you please give me some information about how this payment method is called and possibly some articles I can read up on. Thank you!

答: You can't. You need a payment processor. Paypal is one of many, but you need SOMEONE to process cards for you. Among other issues 'Mastercard' is a global brand, but cards are issued by MANY banks, and to process a card, someone has to route the processing to the proper bank. That's what a payment processor does.</p>

Title: Billing from card directly


问:
Where did the notion of 'calling' a function come from?
I've always wondered why one calls a function as opposed to, for example, executing it.

A Google search for function call etymology and similar terms turns up nothing useful, Wikipedia doesn't mention it, online dictionaries have either no entry at all or no etymology section.

Where did the notion of 'calling' a function come from?

答:
The word call goes back at least to Fortran, the first widely used programming language. In Fortran, CALL is a keyword that passes control to a subroutine. It's not clear why John Backus chose that word to invoke subroutines -- you may need to read one or more biographies of Backus to discover that -- but it seems likely that the use in Fortran is the reason that we use the word call today with respect to functions, methods, etc.

Note that the use of call with respect to functions and other subroutines also fits well with several English-language definitions of call:

to make a brief visit

to demand something

to rouse from sleep

to invite


问:
Which language features are considered harmful?
Please, explain why and list which languages have the (mis)feature implemented As far you know.

Post what you consider a harmful feature, not what you dislike.

答: I'd have to say garbage collection. It does not eliminate the need to think about memory management, but it eliminates the perception of the need to think about memory management, which all too often eliminates the actual thought, and then you get enormous resource hogs and don't know why.  Especially when the behavior of modern generational GCs could be described without too much hyperbole as "one big memory leak by design" anyway.

ContentLicense: CC BY-SA 2.5


答:
You'll need to have an account with a payment processor company. If not PayPal, there are others. Moneris is one.

Usually, your payment processing partner will send you an API which contains the code necessary to submit a payment. You use the API to make calls to the payment processor, but you don't submit raw HTTP requests to them.

You'll might also want to look in to PCI Compliance.

Title: Billing from card directly

Body:
I, for the life of me, cannot find any literature on this, simply because I have no clue how it is called.

I want to learn how to implement a payment option that consists of paying with your credit/debit card directly without the use of a third party like paypal.

This is what I am talking about

Can you please give me some information about how this payment method is called and possibly some articles I can read up on. Thank you!


问:
What does "context-free" mean in the term "context-free grammar"?
Given the amount of material that tries to explain what a context-free grammar (CFG) is, I found it surprising that very few (in my sample, less than 1 in 20) give an explanation on why such grammars are called "context-free". And, to my mind, none succeeds in doing so.

My question is, why are context-free grammars called context-free? What is "the context"? I had an intuition that the context could be other language constructs surrounding the currently analyzed construct, but that seems not to be the case. Could anyone provide a precise explanation?

答:
Context-free grammars do not consider any context for production rules. Context are either terminals or non-terminals.

So: Context-free grammars only have a single non-terminal on the left side of the production rules.


答:
The other answers are quite long, even if accurate and correct. This is the short version.

If you have a string of characters (terminals and nonterminals) and you wish to replace a nonterminal in the string, a context-free grammar allows you to do that regardless of the characters surrounding the nonterminal.

Consider the following rules (lowercase are terminals, uppercase are nonterminals):

```<code>A -> a
AB -> a
</code>```

In the first rule, you can replace an A regardless of what appears around it (context). In the second rule, you cannot replace A unless it is followed by B. While both nonterminals will be replaced in that case, the important point is that the nonterminals surrounding the A matter. One cannot replace BA with a, or B with a: only an A followed by a B because the order, the context of the nonterminals is important. This means the context of a nonterminal matters in the second rule, making it context-sensitive, while the first rule is context-free.

Title: What does "context-free" mean in the term "context-free grammar"?

Body:
Given the amount of material that tries to explain what a context-free grammar (CFG) is, I found it surprising that very few (in my sample, less than 1 in 20) give an explanation on why such grammars are called "context-free". And, to my mind, none succeeds in doing so.

My question is, why are context-free grammars called context-free? What is "the context"? I had an intuition that the context could be other language constructs surrounding the currently analyzed construct, but that seems not to be the case. Could anyone provide a precise explanation?

Body:
The other answers are quite long, even if accurate and correct. This is the short version.

If you have a string of characters (terminals and nonterminals) and you wish to replace a nonterminal in the string, a context-free grammar allows you to do that regardless of the characters surrounding the nonterminal.

Consider the following rules (lowercase are terminals, uppercase are nonterminals):

A -> a
AB -> a

In the first rule, you can replace an A regardless of what appears around it (context). In the second rule, you cannot replace A unless it is followed by B. While both nonterminals will be replaced in that case, the important point is that the nonterminals surrounding the A matter. One cannot replace BA with a, or B with a: only an A followed by a B because the order, the context of the nonterminals is important. This means the context of a nonterminal matters in the second rule, making it context-sensitive, while the first rule is context-free.


问:
When is type testing OK?
Assuming a language with some inherent type safety (e.g., not JavaScript):

Given a method that accepts a SuperType, we know that in most cases wherein we might be tempted to perform type testing to pick an action:

```<code>public void DoSomethingTo(SuperType o) {
  if (o isa SubTypeA) {
    o.doSomethingA()
  } else {
    o.doSomethingB();
  }
}
</code>```

We should usually, if not always, create a single, overridable method on the SuperType and do this:

```<code>public void DoSomethingTo(SuperType o) {
  o.doSomething();
}
</code>```

... wherein each subtype is given its own doSomething() implementation. The rest of our application can then be appropriately ignorant of whether any given SuperType is really a SubTypeA or a SubTypeB.

Wonderful.

But, we're still given is a-like operations in most, if not all, type-safe languages. And that suggests a potential need for explicit type testing.

So, in what situations, if any, should we or must we perform explicit type testing?

Forgive my absent mindedness or lack of creativity. I know I've done it before; but, it was honestly so long ago I can't remember if what I did was good! And in recent memory, I don't think I've encountered a need to test types outside my cowboy JavaScript.

答:
The standard (but hopefully rare) case looks like this: if in the following situation

```<code>public void DoSomethingTo(SuperType o) {
  if (o isa SubTypeA) {
    DoSomethingA((SubTypeA) o )
  } else {
    DoSomethingB((SubTypeB) o );
  }
}
</code>```

the functions DoSomethingA or DoSomethingB cannot easily be implemented as member functions of the inheritance tree of SuperType / SubTypeA/ SubTypeB. For example, if

the subtypes are part of a library which you cannot change, or

if adding the code for DoSomethingXXX to that library would mean to introduce a forbidden dependency.

Note there are often situations where you can circumvent this problem (for example, by creating a wrapper or adapter for SubTypeA and SubTypeB, or trying to re-implement DoSomething completly in terms of basic operations of SuperType), but sometimes these solutions are not worth the hassle or make things more complicated and less extensible than doing the explicit type test.

An example from my yesterdays work: I had a situation where I was going to parallelize the processing of a list of objects (of type SuperType, with exactly two different subtypes, where it is extremely unlikely that there will ever be more). The unparallelized version contained two loops: one loop for objects of subtype A, calling DoSomethingA, and a second loop for objects of subtype B, calling DoSomethingB.

The "DoSomethingA" and "DoSomethingB" methods are both time intensive calculations, using context information which is not available at the scope of the subtypes A and B. (so it makes no sense to implement them as member functions of the subtypes). From the viewpoint of the new "parallel loop", it makes things a lot easier by dealing with them uniformly, so I implemented a function similar to DoSomethingTo from above. However, looking into the implementations of "DoSomethingA" and "DoSomethingB" shows they work very differently internally. So trying to implement a generic "DoSomething" by extending SuperType with a lot of abstract methods was not really going to work, or would mean to overdesign things completely.

Title: When is type testing OK?

Body:
The standard (but hopefully rare) case looks like this: if in the following situation

public void DoSomethingTo(SuperType o) {
  if (o isa SubTypeA) {
    DoSomethingA((SubTypeA) o )
  } else {
    DoSomethingB((SubTypeB) o );
  }
}

the functions DoSomethingA or DoSomethingB cannot easily be implemented as member functions of the inheritance tree of SuperType / SubTypeA/ SubTypeB. For example, if

the subtypes are part of a library which you cannot change, or

if adding the code for DoSomethingXXX to that library would mean to introduce a forbidden dependency.

Note there are often situations where you can circumvent this problem (for example, by creating a wrapper or adapter for SubTypeA and SubTypeB, or trying to re-implement DoSomething completly in terms of basic operations of SuperType), but sometimes these solutions are not worth the hassle or make things more complicated and less extensible than doing the explicit type test.

An example from my yesterdays work: I had a situation where I was going to parallelize the processing of a list of objects (of type SuperType, with exactly two different subtypes, where it is extremely unlikely that there will ever be more). The unparallelized version contained two loops: one loop for objects of subtype A, calling DoSomethingA, and a second loop for objects of subtype B, calling DoSomethingB.

The "DoSomethingA" and "DoSomethingB" methods are both time intensive calculations, using context information which is not available at the scope of the subtypes A and B. (so it makes no sense to implement them as member functions of the subtypes). From the viewpoint of the new "parallel loop", it makes things a lot easier by dealing with them uniformly, so I implemented a function similar to DoSomethingTo from above. However, looking into the implementations of "DoSomethingA" and "DoSomethingB" shows they work very differently internally. So trying to implement a generic "DoSomething" by extending SuperType with a lot of abstract methods was not really going to work, or would mean to overdesign things completely.


答:
When is type checking OK?

Never.

By having the behavior associated with that type in some other function, you're violating the Open Closed Principle, because you're free to modify the existing behavior of the type by changing the is clause, or (in some languages, or depending on the scenario) because you can't extend the type without modifying the internals of the function doing the is check.

More importantly, is checks are a strong sign that you're violating the Liskov Substitution Principle. Anything that works with SuperType should be completely ignorant of what sub types there may be.

You're implicitly associating some behavior with the type's name. This makes your code harder to maintain because these implicit contracts are spread throughout the code and not guaranteed to be universally and consistently enforced like actual class members are.

All that said, is checks can be less bad than other alternatives. Putting all common functionality into a base class is heavy-handed and often leads to worse problems. Using a single class that has a flag or enum for what "type" the instance is... is worse than horrible, since you're now spreading the type system circumvention to all consumers.

In short, you should always consider type checks to be a strong code smell. But as with all guidelines, there will be times when you're forced to choose between which guideline violation is the least offensive.

Title: When is type testing OK?

Body:
Assuming a language with some inherent type safety (e.g., not JavaScript):

Given a method that accepts a SuperType, we know that in most cases wherein we might be tempted to perform type testing to pick an action:

```<code>public void DoSomethingTo(SuperType o) {
  if (o isa SubTypeA) {
    o.doSomethingA()
  } else {
    o.doSomethingB();
  }
}
</code>```

We should usually, if not always, create a single, overridable method on the SuperType and do this:

```<code>public void DoSomethingTo(SuperType o) {
  o.doSomething();
}
</code>```

... wherein each subtype is given its own doSomething() implementation. The rest of our application can then be appropriately ignorant of whether any given SuperType is really a SubTypeA or a SubTypeB.

Wonderful.

But, we're still given is a-like operations in most, if not all, type-safe languages. And that suggests a potential need for explicit type testing.

So, in what situations, if any, should we or must we perform explicit type testing?

Forgive my absent mindedness or lack of creativity. I know I've done it before; but, it was honestly so long ago I can't remember if what I did was good! And in recent memory, I don't think I've encountered a need to test types outside my cowboy JavaScript.


答:
The main situation I've ever needed it was when comparing two objects, such as in an equals(other) method, which might require different algorithms depending on the exact type of other.  Even then, it's fairly rare.

The other situation I've had it come up, again very rarely, is after deserialization or parsing, where you sometimes need it to safely cast to a more specific type.

Also, sometimes you just need a hack to work around third party code you don't control.  It's one of those things you don't really want to use on a regular basis, but are glad it's there when you really need it.

Title: When is type testing OK?


答:
I would agree with Karl Bielefeldt's answer to move doStuff to the SuperClass with different implementations in SubA and SubB, or more specifically keep doStuff where you have it and only call methods on the passed in SuperClass object in the places where the the implementation differs for SubA and SubB:

```<code>public void doStuff(SuperClass object){
    // do common stuff here

    object.specificStuff(<whatever parameters>);

    // do more common stuff here

    int bar = object.moreSpecificStuff(<some parameters>);

    // room for still more common stuff, perhabs based on bar's value
}
</code>```

Then Superclass would have abstract (or pure virtual) methods:

```<code>class SuperClass {

   ( ... )

   virtual void specificStuff( <whatever parameters> ) = 0;  // assuming C++

   virtual int moreSpecificStuff(<some parameters>) = 0;  // assuming C++

};
</code>```

and SubA and SubB would provide implementations for those.

This is one way to implement the strategy pattern (from the Design Patterns book, Go4).

Body:
I would agree with Karl Bielefeldt's answer to move doStuff to the SuperClass with different implementations in SubA and SubB, or more specifically keep doStuff where you have it and only call methods on the passed in SuperClass object in the places where the the implementation differs for SubA and SubB:

public void doStuff(SuperClass object){
    // do common stuff here

    object.specificStuff(<whatever parameters>);

    // do more common stuff here

    int bar = object.moreSpecificStuff(<some parameters>);

    // room for still more common stuff, perhabs based on bar's value
}

Then Superclass would have abstract (or pure virtual) methods:

class SuperClass {

   ( ... )

   virtual void specificStuff( <whatever parameters> ) = 0;  // assuming C++

   virtual int moreSpecificStuff(<some parameters>) = 0;  // assuming C++

};

and SubA and SubB would provide implementations for those.

This is one way to implement the strategy pattern (from the Design Patterns book, Go4).


答:
Type testing and type casting are two very closely related concepts. So closely related that I feel confident in saying that you should never do a type test unless your intent is to type cast the object based on the result.

When you think about ideal Object-Oriented design, type testing (and casting) should never happen. But hopefully by now you've figured out that Object-Oriented programming is not ideal. Sometimes, especially with lower-level code, the code can't stay true to the ideal. This is the case with ArrayLists in Java; since they don't know at run-time what class is being stored in the array, they create Object[] arrays and statically cast them to the correct type.

It's been pointed out that a common need to type testing (and type casting) comes from the Equals method, which in most languages is supposed to take a plain Object. The implementation should have some detailed checks to make if the two objects are the same type, which requires being able to test what type they are.

Type testing also comes up frequently in reflection. Often you will have methods that return Object[] or some other generic array, and you want to pull out all the Foo objects for whatever reason. This is a perfectly legitimate use of type testing and casting.

In general, type testing is bad when it needlessly couples your code to how a specific implementation was written. This can easily lead to needing a specific test for each type or combination of types, such as if you want to find the intersection of lines, rectangles, and circles, and the intersection function has a different algorithm for each combination. Your goal is to put any details specific to one kind of object in the same place as that object, because that will make it easier to maintain and extend your code.

Title: When is type testing OK?


问:
Where to store front-end data for "object calculator"
I recently have completed a language library that acts as a giant filter for food items, and flows a bit like this :Products -> Recipes -> MenuItems -> Meals and finally, upon submission, creates an Order.

I have also completed a database structure that stores all the pertinent information to each class, and seems to fit my needs.

The issue I'm having is linking the two. I imagined all of the information being local to each instance of the product, where there exists one backend user who edits and manipulates data, and multiple front end users who select their Meal(s) to create an Order. Ideally, all of the front end users would have all of this information stored locally within the library, and would update the library on startup from a database.

How should I go about storing the data so that I can load it into the library every time the user opens the application? Do I package a database onboard and just load and populate every time?

The only method I can currently conceive of doing this, even if I only have 500 possible Product objects, would require me to foreach the list for every Product that I need to match to a Recipe and so on and so forth every time I relaunch the program, which seems like a lot of wasteful loading.

Here is a general flow of my architecture:

Products:

```<code>public class Product : IPortionable
{
    public Product(string n, uint pNumber = 0)
    {
        name = n;
        productNumber = pNumber;
    }

    public string name { get; set; }
    public uint productNumber { get; set; }
}
</code>```

Recipes:

```<code>public Recipe(string n, decimal yieldAmt, Volume.Unit unit)
    {
        name = n;
        yield = new Volume(yieldAmt, unit);
        yield.ConvertUnit();
    }
    /// <summary>
    /// Creates a new ingredient object
    /// </summary>
    /// <param name="n">Name</param>
    /// <param name="yieldAmt">Recipe Yield</param>
    /// <param name="unit">Unit of Yield</param>
    public Recipe(string n, decimal yieldAmt, Weight.Unit unit)
    {
        name = n;
        yield = new Weight(yieldAmt, unit);
    }

    public Recipe(Recipe r)
    {
        name = r.name;
        yield = r.yield;
        ingredients = r.ingredients;
    }

    public string name { get; set; }
    public IMeasure yield;

    public Dictionary<IPortionable, IMeasure> ingredients = new Dictionary<IPortionable,IMeasure>();
</code>```

MenuItems:

```<code>public abstract class MenuItem : IScalable
{
    public static string title = null;

    public string name { get; set; }
    public decimal maxPortionSize { get; set; }
    public decimal minPortionSize { get; set; }

    public Dictionary<IPortionable, IMeasure> ingredients = new Dictionary<IPortionable, IMeasure>();
</code>```

and Meal:

```<code>public class Meal
{
    public Meal(int guests)
    {
        guestCount = guests;
    }

    public int guestCount { get; private set; }

    //TODO: Make a new MainCourse class that holds pasta and Entree
    public Dictionary<string, int> counts = new Dictionary<string, int>(){
       {MainCourse.title, 0},
       {Side.title , 0},
       {Appetizer.title, 0}
    };

    public List<MenuItem> items = new List<MenuItem>();
</code>```

The Database just stores and links each of these basic names and amounts together usings ID's (RecipeID, ProductID and MenuItemID)

答:
There are certainly various strategies to solve this problem.

One possible way is to do it client-server.

Use case model:

The front-end app will be desktop app installed on user's device without its own database.
When front-end user needs to select from menuitems it will invoke GetMenuItems method on the server and will receive all the menu items (without links to Products and Recipes).

Then the front-end user creates collection of Meals form available MenuItems. When he finishes with it, he posts his choice to server by invoking MakeOrder method with Meals collection as a parameter.

The server will create only instances of objects (of classes Product, Recipe, MenuItem) that are necessary to complete requested calculation. I suppose that from given MenuItem you can select only relevant Recipes and relevat Rroducts. Only optionally server can cache all Product, Recipe, MenuItem instances in memory.

Then the result of the calculation will be then presented on client.


答:
"Never" is the canonical answer to "when is type testing okay?"
There's no
way to prove or disprove this; it is part of a system of beliefs about what
makes "good design" or "good object-oriented design." It's also hokum.

To be sure, if you have an integrated set of classes
and also more than one or two functions that need that kind of
direct type testing, you're probably
DOING IT WRONG. What you really need is a method that's implemented differently in
SuperType and its subtypes. This is part and parcel of object-oriented
programming, and the whole reason classes and inheritance exist.

In this case, explicitly type-testing is wrong not because type testing is
inherently wrong, but because the language already
has a clean, extensible, idiomatic way of accomplishing type
discrimination, and you didn't use it. Instead, you fell back to a
primitive, fragile, non-extensible idiom.

Solution: Use the idiom. As you
suggested, add a method to each of the classes, then let standard inheritance
and method-selection algorithms determine which case applies. Or if you can't
change the base types, subclass and add your method there.

So much for the conventional wisdom, and on to some answers. Some cases where
explicit type testing makes sense:

It's a one-off. If you had a lot of type discrimination to do,
you might extend the types, or subclass. But you don't. You have just
one or two places where you need explicit testing, so it's not worth
your while to go back and work through the class hierarchy to add
the functions as methods. Or it's not worth the practical effort to
add the kind of generality, testing, design reviews, documentation,
or other attributes of the base classes for such a simple, limited
usage. In that case, adding a function that does direct testing is rational.

You can't adjust the classes. You think about subclassing--but you can't.
Many classes in Java, for
instance, are designated final.
You try to throw in a public class ExtendedSubTypeA extends SubTypeA {...}
and the compiler tells you, in no uncertain terms, that what you're doing is
not possible. Sorry, grace and sophistication of the object oriented model!
Someone decided you can't extend their types! Unfortunately, many of the standard library
are final, and making classes final is common design guidance.
A function end-run is what's left available to you.

BTW, this isn't limited to statically typed languages. Dynamic language Python has a number of
base classes that, under the covers implemented in C, cannot really be modified.
Like Java, that includes most of the standard types.

Your code is external. You are developing with classes and objects that come
from a range of database servers, middleware engines, and other codebases you can't
control or adjust. Your code is just a lowly consumer of objects generated elsewhere.
Even if you could subclass SuperType, you're not going to be able to get those
libraries on which you depend to generate objects in your subclasses. They're
going to hand you instances of the types they know, not your variants. This
isn't always the case...sometimes they are built for flexibility, and they dynamically
instantiate instances of classes that you feed them. Or they provide a mechanism to
register the subclasses you want their factories to construct. XML parsers seem particularly good at
providing such entry points; see e.g. a JAXB example in Java
or lxml in Python. But most code bases do not
provide
such extensions. They're going to hand you back the classes they were built with and
know about. It generally will not make sense to proxy their results into your custom
results just so you can use a purely object-oriented type selector.
If you're going to do type discrimination, you're going to have to do it
relatively crudely. Your type testing code then looks quite appropriate.

Poor person's generics/multiple dispatch. You want to accept a variety of different types to your
code, and feel that having an array of very type-specific methods isn't graceful.
public void add(Object x) seems logical, but not an array of
addByte, addShort, addInt, addLong,
addFloat, addDouble, addBoolean, addChar, and addString variants (to
name a few). Having functions or methods that take a high super-type and then
determine what to do on a type-by-type basis--they're not going to win you the
Purity Award at the annual Booch-Liskov Design Symposium, but
dropping the Hungarian naming
will give you a simpler API. In a sense, your is-a or is-instance-of testing
is simulating generic or multi-dispatch in a language context that doesn't natively
support it.

Built-in language support for both
generics and
duck typing reduce the need
for type checking
by making "do something graceful and appropriate" more likely. The multiple
dispatch / interface selection
seen in languages like Julia and Go similarly replace direct type testing with
built-in mechanisms for type-based selection of "what to do."
But not all languages support these. Java e.g. is generally single-dispatch,
and its idioms are not super-friendly to duck typing.

But even with all these type discrimination features--inheritance, generics, duck typing,
and
multiple-dispatch--it's sometimes just convenient to have a single, consolidated
routine that makes the fact that you are doing something based on the type of the
object clear and immediate. In metaprogramming
I have found it essentially unavoidable. Whether falling back to
direct type inquires constitutes "pragmatism in action" or "dirty coding"
will depend on your design philosophy and beliefs.

Title: When is type testing OK?


问:
Falsy values vs null, undefined, or empty string
I've worked with jQuery over the years. However, recently, I've found myself getting deeper into the JavaScript language. Recently, I've heard about "truthy" and falsey values. However, I don't fully understand them. Currently, I have some code that looks like this:

```<code>var fields = options.fields || ['id', 'query'];
</code>```

I need to identify if fields is null, undefined, or has a length of 0. I know the long way is to do:

```<code>if ((fields === null) || (fields === undefined) || (fields.length === 0)) {
 ...
}
</code>```

My question is, is the following the same:

```<code>if (!fields)  {
 ...
}
</code>```

答:
In programming, truthiness or falsiness is that quality of those boolean expressions which don't resolve to an actual boolean value, but which nevertheless get interpreted as a boolean result.

In the case of C, any expression that evaluates to zero is interpreted to be false.  In Javascript, the expression value in

```<code>if(value) {
}
</code>```

will evaluate to true if value is not:

```<code>null
undefined
NaN
empty string ("")
0
false
</code>```

See Also

Is there a standard function to check for null, undefined, or blank variables in JavaScript?

Body:
In programming, truthiness or falsiness is that quality of those boolean expressions which don't resolve to an actual boolean value, but which nevertheless get interpreted as a boolean result.

In the case of C, any expression that evaluates to zero is interpreted to be false.  In Javascript, the expression value in

if(value) {
}

will evaluate to true if value is not:

null
undefined
NaN
empty string ("")
0
false

See Also

Is there a standard function to check for null, undefined, or blank variables in JavaScript?


答:
As Uncle Bob calls it:

```<code>When your compiler forgets about the type.
</code>```

In one of his Clean Coder episodes he gave an example of a function call that is used to return Employees. Manager is a sub-type of Employee. Let's assume we have an application service that accepts a Manager's id and summons him to office :) The function getEmployeeById() return a super-type Employee , but I want to check if a manager is returned in this use-case.

For example:

```<code>var manager = employeeRepository.getEmployeeById(empId);
if (!(manager is Manager))
   throw new Exception("Invalid Id specified.");
manager.summon();
</code>```

Here I'm checking to see if the employee returned by query is actually a manager (i.e. I expect it to be a manager and if otherwise fail fast).

Not the best example, but it's uncle Bob after all.

Update

I updated the example as much as I can remember from memory.

Title: When is type testing OK?

Body:
As Uncle Bob calls it:

When your compiler forgets about the type.

In one of his Clean Coder episodes he gave an example of a function call that is used to return Employees. Manager is a sub-type of Employee. Let's assume we have an application service that accepts a Manager's id and summons him to office :) The function getEmployeeById() return a super-type Employee , but I want to check if a manager is returned in this use-case.

For example:

var manager = employeeRepository.getEmployeeById(empId);
if (!(manager is Manager))
   throw new Exception("Invalid Id specified.");
manager.summon();

Here I'm checking to see if the employee returned by query is actually a manager (i.e. I expect it to be a manager and if otherwise fail fast).

Not the best example, but it's uncle Bob after all.

Update

I updated the example as much as I can remember from memory.


答:
I think you can use the visitor pattern here. The class with the doStuff method should implement the Visitor interface. This interface has overloaded doStuff(..) (or visit) methods for all subtypes of the SuperClass. The SuperClass has an abstract method accept(Visitor) method and all subclasses implement this by visitor.doStuff(this), calling the correct method on the visitor.

This pattern is a fix for the static binding that e.g. Java has: method calls are only dynamic with respect to the type of object they are called on, not the parameter types.


问:
How often do CPUs make calculation errors?
In Dijkstra's Notes on Structured Programming he talks a lot about the provability of computer programs as abstract entities. As a corollary, he remarks how testing isn't enough. E.g., he points out the fact that it would be impossible to test a multiplication function f(x,y) = x*y for any large values of x and y across the entire ranges of x and y. My question concerns his misc. remarks on "lousy hardware". I know the essay was written in the 1970s when computer hardware was less reliable, but computers still aren't perfect, so they must make calculation mistakes sometimes. Does anybody know how often this happens or if there are any statistics on this?

答:
The following content may be about calculation errors in GPUs.

Given enough time, Intel i7-3610QM and an Nvidia GeForce GTX 660 will disagree with one another given the same instructions. (cuda 5.5, compute_20,sm_20)

So, one is left to conclude that one of the two makes an error.

During a particle simulation feasibility study benchmark I noticed that after a thousand or so double precision transformations (transformations including sin, cos, multiplication, division, addition and subtraction) errors started creeping in.

I'll give you a small excerpt of numbers to compare (first number is always CPU, second GPU)

```<code>-1.4906010142701069
-1.4906010142701074

-161011564.55005690
-161011564.55005693

-0.13829959396003652
-0.13829959396003658

-16925804.720949132
-16925804.720949136

-36.506235247679221
-36.506235247679228

-3.3870884719850887
-3.3870884719850896
</code>```

(note that not every transformation sequence yields an error)

While the maximum error is almost negligible (0.0000000000000401%) it still exists, and does contribute to cumulative error.

Now this error might be due to a difference in implementation of one of the intrinsic libraries. Indeed, it looks like the GPU prefers to round down or truncate where the CPU rounds up. Curiously too, this only seems to happen on negative numbers.

But the point is that identical instructions are not necessarily guaranteed to return identical results, even on digital machines.

I hope this contributed.

EDIT as a sidenote:
In the case of GPU arithmetic errors, this (ctrl+f "First GPU with ECC Memory Support") could also be of interest, although not necessarily relevant to the errors above.

Body:
The following content may be about calculation errors in GPUs.

Given enough time, Intel i7-3610QM and an Nvidia GeForce GTX 660 will disagree with one another given the same instructions. (cuda 5.5, compute_20,sm_20)

So, one is left to conclude that one of the two makes an error.

During a particle simulation feasibility study benchmark I noticed that after a thousand or so double precision transformations (transformations including sin, cos, multiplication, division, addition and subtraction) errors started creeping in.

I'll give you a small excerpt of numbers to compare (first number is always CPU, second GPU)

-1.4906010142701069
-1.4906010142701074

-161011564.55005690
-161011564.55005693

-0.13829959396003652
-0.13829959396003658

-16925804.720949132
-16925804.720949136

-36.506235247679221
-36.506235247679228

-3.3870884719850887
-3.3870884719850896

(note that not every transformation sequence yields an error)

While the maximum error is almost negligible (0.0000000000000401%) it still exists, and does contribute to cumulative error.

Now this error might be due to a difference in implementation of one of the intrinsic libraries. Indeed, it looks like the GPU prefers to round down or truncate where the CPU rounds up. Curiously too, this only seems to happen on negative numbers.

But the point is that identical instructions are not necessarily guaranteed to return identical results, even on digital machines.

I hope this contributed.

EDIT as a sidenote:
In the case of GPU arithmetic errors, this (ctrl+f "First GPU with ECC Memory Support") could also be of interest, although not necessarily relevant to the errors above.