面向问答串的 Stack Overflow 抓取 API

markdown
# Why is conditional processing of a sorted array faster than of an unsorted array?
​
Score: 27544 · Views: 1,999,328 · Asked: 2012-06-27 · By: GManNickG · Tags: java, c++, performance, cpu-architecture, branch-prediction · Answers: 25
​
In this C++ code, sorting the data (_before_ the timed region) makes the primary loop ~6x faster:
​
```
#include <algorithm>
#include <ctime>
#include <iostream>
​
int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];
​
    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;
​
    // !!! With this, the next loop runs faster.
    std::sort(data, data + arraySize);
​
    // Test
    clock_t start = clock();
    long long sum = 0;
    for (unsigned i = 0; i < 100000; ++i)
    {
        for (unsigned c = 0; c < arraySize; ++c)
        {   // Primary loop.
            if (data[c] >= 128)
                sum += data[c];
        }
    }
​
    double elapsedTime = static_cast<double>(clock()-start) / CLOCKS_PER_SEC;
​
    std::cout << elapsedTime << '\n';
    std::cout << "sum = " << sum << '\n';
}
```
​
*   Without `std::sort(data, data + arraySize);`, the code runs in 11.54 seconds.
*   With the sorted data, the code runs in 1.93 seconds.
​
(Sorting itself takes more time than this one pass over the array, so it's not actually worth doing if we needed to calculate this for an unknown array.)
​
* * *
​
Initially, I thought this might be just a language or compiler anomaly, so I tried Java:
​
```
import java.util.Arrays;
import java.util.Random;
​
public class Main
{
    public static void main(String[] args)
    {
        // Generate data
        int arraySize = 32768;
        int data[] = new int[arraySize];
​
        Random rnd = new Random(0);
        for (int c = 0; c < arraySize; ++c)
            data[c] = rnd.nextInt() % 256;
​
        // !!! With this, the next loop runs faster
        Arrays.sort(data);
​
        // Test
        long start = System.nanoTime();
        long sum = 0;
        for (int i = 0; i < 100000; ++i)
        {
            for (int c = 0; c < arraySize; ++c)
            {   // Primary loop.
                if (data[c] >= 128)
                    sum += data[c];
            }
        }
​
        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}
```
​
With a similar but less extreme result.
​
* * *
​
My first thought was that sorting brings the data into the [cache](https://en.wikipedia.org/wiki/CPU_cache), but that's silly because the array was just generated.
​
*   What is going on?
*   Why is processing a sorted array faster than processing an unsorted array?
​
The code is summing up some independent terms, so the order should not matter.
​
* * *
​
## Related / follow-up Q&As with more modern C++ compilers
​
*   [Why is processing an unsorted array the same speed as processing a sorted array with modern x86-64 clang?](https://stackoverflow.com/q/66521344) - **modern C++ compilers auto-vectorize the loop**, especially when SSE4.1 or AVX2 is available. This avoids any data-dependent branching so performance isn't data-dependent.
*   [gcc optimization flag -O3 makes code slower than -O2](https://stackoverflow.com/q/28875325) - branchless scalar with `cmov` can result in a longer dependency chain (especially when GCC chooses poorly), creating a latency bottleneck that makes it slower than branchy asm for the sorted case.
​
## Answers (25)
​
### ✅ Accepted · Score: 35296 · By: Mysticial · Answered: 2012-06-27
​
**You are a victim of [branch prediction](https://en.wikipedia.org/wiki/Branch_predictor) fail.**
​
* * *
​
## What is Branch Prediction?
​
Consider a railroad junction:
​
 [Image](https://commons.wikimedia.org/wiki/File:Entroncamento_do_Transpraia.JPG) by Mecanismo, via Wikimedia Commons. Used under the [CC-By-SA 3.0](https://creativecommons.org/licenses/by-sa/3.0/deed.en) license.
​
Now for the sake of argument, suppose this is back in the 1800s - before long-distance or radio communication.
​
You are a blind operator of a junction and you hear a train coming. You have no idea which way it is supposed to go. You stop the train to ask the driver which direction they want. And then you set the switch appropriately.
​
_Trains are heavy and have a lot of inertia, so they take forever to start up and slow down._
​
Is there a better way? You guess which direction the train will go!
​
*   If you guessed right, it continues on.
*   If you guessed wrong, the driver will stop, back up, and yell at you to flip the switch. Then it can restart down the other path.
​
**If you guess right every time**, the train will never have to stop.
**If you guess wrong too often**, the train will spend a lot of time stopping, backing up, and restarting.
​
* * *
​
**Consider an if-statement:** At the processor level, it is a branch instruction:
​
if(x >= 128) compiles into a jump-if-less-than processor instruction.
​
You are a processor and you see a branch. You have no idea which way it will go. What do you do? You halt execution and wait until the previous instructions are complete. Then you continue down the correct path.
​
_Modern processors are complicated and have long pipelines. This means they take forever to "warm up" and "slow down"._
​
Is there a better way? You guess which direction the branch will go!
​
*   If you guessed right, you continue executing.
*   If you guessed wrong, you need to flush the pipeline and roll back to the branch. Then you can restart down the other path.
​
**If you guess right every time**, the execution will never have to stop.
**If you guess wrong too often**, you spend a lot of time stalling, rolling back, and restarting.
​
* * *
​
This is branch prediction. I admit it's not the best analogy since the train could just signal the direction with a flag. But in computers, the processor doesn't know which direction a branch will go until the last moment.
​
How would you strategically guess to minimize the number of times that the train must back up and go down the other path? You look at the past history! If the train goes left 99% of the time, then you guess left. If it alternates, then you alternate your guesses. If it goes one way every three times, you guess the same...
​
_**In other words, you try to identify a pattern and follow it.**_ This is more or less how branch predictors work.
​
Most applications have well-behaved branches. Therefore, modern branch predictors will typically achieve >90% hit rates. But when faced with unpredictable branches with no recognizable patterns, branch predictors are virtually useless.
​
Further reading: ["Branch predictor" article on Wikipedia](https://en.wikipedia.org/wiki/Branch_predictor).
​
* * *
​
## As hinted from above, the culprit is this if-statement:
​
```
if (data[c] >= 128)
    sum += data[c];
```
​
Notice that the data is evenly distributed between 0 and 255. When the data is sorted, roughly the first half of the iterations will not enter the if-statement. After that, they will all enter the if-statement.
​
This is very friendly to the branch predictor since the branch consecutively goes the same direction many times. Even a simple saturating counter will correctly predict the branch except for the few iterations after it switches direction.
​
**Quick visualization:**
​
```
T = branch taken
N = branch not taken
​
data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N  N  N  N  N  ...   N    N    T    T    T  ...   T    T    T  ...
​
       = NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT  (easy to predict)
```
​
However, when the data is completely random, the branch predictor is rendered useless, because it can't predict random data. Thus there will probably be around 50% misprediction (no better than random guessing).
​
```
data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118,  14, 150, 177, 182, ...
branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T  ...
​
       = TTNTTTTNTNNTTT ...   (completely random - impossible to predict)
```
​
* * *
​
**What can be done?**
​
If the compiler isn't able to optimize the branch into a conditional move, you can try some hacks if you are willing to sacrifice readability for performance.
​
Replace:
​
```
if (data[c] >= 128)
    sum += data[c];
```
​
with:
​
```
int t = (data[c] - 128) >> 31;
sum += ~t & data[c];
```
​
This eliminates the branch and replaces it with some bitwise operations.
​
(Note that this hack is not strictly equivalent to the original if-statement. But in this case, it's valid for all the input values of `data[]`.)
​
**Benchmarks: Core i7 920 @ 3.5 GHz**
​
C++ - Visual Studio 2010 - x64 Release
​
Scenario
​
Time (seconds)
​
Branching - Random data
​
11.777
​
Branching - Sorted data
​
2.352
​
Branchless - Random data
​
2.564
​
Branchless - Sorted data
​
2.587
​
Java - NetBeans 7.1.1 JDK 7 - x64
​
Scenario
​
Time (seconds)
​
Branching - Random data
​
10.93293813
​
Branching - Sorted data
​
5.643797077
​
Branchless - Random data
​
3.113581453
​
Branchless - Sorted data
​
3.186068823
​
Observations:
​
*   **With the Branch:** There is a huge difference between the sorted and unsorted data.
*   **With the Hack:** There is no difference between sorted and unsorted data.
*   In the C++ case, the hack is actually a tad slower than with the branch when the data is sorted.
​
A general rule of thumb is to avoid data-dependent branching in critical loops (such as in this example).
​
* * *
​
**Update:**
​
*   GCC 4.6.1 with `-O3` or `-ftree-vectorize` on x64 is able to generate a conditional move, so there is no difference between the sorted and unsorted data - both are fast. This is called "if-conversion" (to branchless) and is necessary for vectorization but also sometimes good for scalar.
​
    (Or somewhat fast: for the already-sorted case, `cmov` can be slower especially if GCC puts it on the critical path instead of just `add`, especially on Intel before Broadwell where `cmov` has 2-cycle latency: _[gcc optimization flag -O3 makes code slower than -O2](https://stackoverflow.com/questions/28875325/gcc-optimization-flag-o3-makes-code-slower-than-o2)_)
​
*   VC++ 2010 is unable to generate conditional moves for this branch even under `/Ox`.
​
*   [Intel C++ Compiler](https://en.wikipedia.org/wiki/Intel_C++_Compiler) (ICC) 11 does something miraculous. It [interchanges the two loops](https://en.wikipedia.org/wiki/Loop_interchange), thereby hoisting the unpredictable branch to the outer loop. Not only is it immune to the mispredictions, it's also twice as fast as whatever VC++ and GCC can generate! In other words, ICC took advantage of the test-loop to defeat the benchmark...
​
*   If you give the Intel compiler the branchless code, it just outright vectorizes it... and is just as fast as with the branch (with the loop interchange).
​
*   Clang also vectorizes the `if()` version, as will GCC 5 and later with `-O3`, even though it takes quite a few instructions to sign-extend to the 64-bit sum on x86 without SSE4 or AVX2. (`-march=x86-64-v2` or `v3`). See _[Why is processing an unsorted array the same speed as processing a sorted array with modern x86-64 clang?](https://stackoverflow.com/questions/66521344/why-is-processing-an-unsorted-array-the-same-speed-as-processing-a-sorted-array)_
​
This goes to show that even mature modern compilers can vary wildly in their ability to optimize code...
​
### Score: 4767 · By: Daniel Fischer · Answered: 2012-06-27
​
**Branch prediction.**
​
With a sorted array, the condition `data[c] >= 128` is first `false` for a streak of values, then becomes `true` for all later values. That's easy to predict. With an unsorted array, you pay for the branching cost.
​
### Score: 3860 · By: WiSaGaN · Answered: 2012-06-28
​
The reason why performance improves drastically when the data is sorted is that the branch prediction penalty is removed, as explained beautifully in [Mysticial's answer](//stackoverflow.com/questions/11227809/why-is-it-faster-to-process-a-sorted-array-than-an-unsorted-array/11227902#11227902).
​
Now, if we look at the code
​
```
if (data[c] >= 128)
    sum += data[c];
```
​
we can find that the meaning of this particular `if... else...` branch is to add something when a condition is satisfied. This type of branch can be easily transformed into a **conditional move** statement, which would be compiled into a conditional move instruction: `cmovl`, in an `x86` system. The branch and thus the potential branch prediction penalty is removed.
​
In `C`, thus `C++`, the statement, which would compile directly (without any optimization) into the conditional move instruction in `x86`, is the ternary operator `... ? ... : ...`. So we rewrite the above statement into an equivalent one:
​
```
sum += data[c] >=128 ? data[c] : 0;
```
​
While maintaining readability, we can check the speedup factor.
​
On an Intel [Core i7](//en.wikipedia.org/wiki/Intel_Core#Core_i7)\-2600K @ 3.4 GHz and Visual Studio 2010 Release Mode, the benchmark is:
​
**x86**
​
Scenario
​
Time (seconds)
​
Branching - Random data
​
8.885
​
Branching - Sorted data
​
1.528
​
Branchless - Random data
​
3.716
​
Branchless - Sorted data
​
3.71
​
**x64**
​
Scenario
​
Time (seconds)
​
Branching - Random data
​
11.302
​
Branching - Sorted data
​
1.830
​
Branchless - Random data
​
2.736
​
Branchless - Sorted data
​
2.737
​
The result is robust in multiple tests. We get a great speedup when the branch result is unpredictable, but we suffer a little bit when it is predictable. In fact, when using a conditional move, the performance is the same regardless of the data pattern.
​
Now let's look more closely by investigating the `x86` assembly they generate. For simplicity, we use two functions `max1` and `max2`.
​
`max1` uses the conditional branch `if... else ...`:
​
```
int max1(int a, int b) {
    if (a > b)
        return a;
    else
        return b;
}
```
​
`max2` uses the ternary operator `... ? ... : ...`:
​
```
int max2(int a, int b) {
    return a > b ? a : b;
}
```
​
On an x86-64 machine, `GCC -S` generates the assembly below.
​
```
:max1
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    -8(%rbp), %eax
    jle     .L2
    movl    -4(%rbp), %eax
    movl    %eax, -12(%rbp)
    jmp     .L4
.L2:
    movl    -8(%rbp), %eax
    movl    %eax, -12(%rbp)
.L4:
    movl    -12(%rbp), %eax
    leave
    ret
​
:max2
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    %eax, -8(%rbp)
    cmovge  -8(%rbp), %eax
    leave
    ret
```
​
`max2` uses much less code due to the usage of instruction `cmovge`. But the real gain is that `max2` does not involve branch jumps, `jmp`, which would have a significant performance penalty if the predicted result is not right.
​
So why does a conditional move perform better?
​
In a typical `x86` processor, the execution of an instruction is divided into several stages. Roughly, we have different hardware to deal with different stages. So we do not have to wait for one instruction to finish to start a new one. This is called **[pipelining](//en.wikipedia.org/wiki/Pipeline_\(computing\))**.
​
In a branch case, the following instruction is determined by the preceding one, so we cannot do pipelining. We have to either wait or predict.
​
In a conditional move case, the execution of conditional move instruction is divided into several stages, but the earlier stages like `Fetch` and `Decode` do not depend on the result of the previous instruction; only the latter stages need the result. Thus, we wait a fraction of one instruction's execution time. This is why the conditional move version is slower than the branch when the prediction is easy.
​
The book _[Computer Systems: A Programmer's Perspective, second edition](https://rads.stackoverflow.com/amzn/click/com/0136108040)_ explains this in detail. You can check Section 3.6.6 for _Conditional Move Instructions_, entire Chapter 4 for _Processor Architecture_, and Section 5.11.2 for special treatment for _Branch Prediction and Misprediction Penalties_.
​
Sometimes, some modern compilers can optimize our code to assembly with better performance, and sometimes some compilers can't (the code in question is using Visual Studio's native compiler). Knowing the performance difference between a branch and a conditional move when unpredictable can help us write code with better performance when the scenario gets so complex that the compiler can not optimize them automatically.
​
### Score: 2672 · By: vulcan raven · Answered: 2012-07-03
​
If you are curious about even more optimizations that can be done to this code, consider this:
​
Starting with the original loop:
​
```
for (unsigned i = 0; i < 100000; ++i)
{
    for (unsigned j = 0; j < arraySize; ++j)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}
```
​
With loop interchange, we can safely change this loop to:
​
```
for (unsigned j = 0; j < arraySize; ++j)
{
    for (unsigned i = 0; i < 100000; ++i)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}
```
​
Then, you can see that the `if` conditional is constant throughout the execution of the `i` loop, so you can hoist the `if` out:
​
```
 for (unsigned j = 0; j < arraySize; ++j)
 {
     if (data[j] >= 128)
     {
         for (unsigned i = 0; i < 100000; ++i)
         {
             sum += data[j];
         }
    }
}
```
​
Then, you see that the inner loop can be collapsed into one single expression, assuming the floating point model allows it (`/fp:fast` is thrown, for example)
​
```
for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        sum += data[j] * 100000;
    }
}
```
​
That one is 100,000 times faster than before.
​
### Score: 2214 · By: caf · Answered: 2012-10-12
​
No doubt some of us would be interested in ways of identifying code that is problematic for the CPU's branch-predictor. The Valgrind tool `cachegrind` has a branch-predictor simulator, enabled by using the `--branch-sim=yes` flag. Running it over the examples in this question, with the number of outer loops reduced to 10000 and compiled with `g++`, gives these results:
​
**Sorted:**
​
```
==32551== Branches:        656,645,130  (  656,609,208 cond +    35,922 ind)
==32551== Mispredicts:         169,556  (      169,095 cond +       461 ind)
==32551== Mispred rate:            0.0% (          0.0%     +       1.2%   )
```
​
**Unsorted:**
​
```
==32555== Branches:        655,996,082  (  655,960,160 cond +  35,922 ind)
==32555== Mispredicts:     164,073,152  (  164,072,692 cond +     460 ind)
==32555== Mispred rate:           25.0% (         25.0%     +     1.2%   )
```
​
Drilling down into the line-by-line output produced by `cg_annotate` we see for the loop in question:
​
**Sorted:**
​
```
          Bc    Bcm Bi Bim
      10,001      4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .      .  .   .      {
           .      .  .   .          // primary loop
 327,690,000 10,016  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .      .  .   .          {
 327,680,000 10,006  0   0              if (data[c] >= 128)
           0      0  0   0                  sum += data[c];
           .      .  .   .          }
           .      .  .   .      }
```
​
**Unsorted:**
​
```
          Bc         Bcm Bi Bim
      10,001           4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .           .  .   .      {
           .           .  .   .          // primary loop
 327,690,000      10,038  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .           .  .   .          {
 327,680,000 164,050,007  0   0              if (data[c] >= 128)
           0           0  0   0                  sum += data[c];
           .           .  .   .          }
           .           .  .   .      }
```
​
This lets you easily identify the problematic line - in the unsorted version the `if (data[c] >= 128)` line is causing 164,050,007 mispredicted conditional branches (`Bcm`) under cachegrind's branch-predictor model, whereas it's only causing 10,006 in the sorted version.
​
* * *
​
Alternatively, on Linux you can use the performance counters subsystem to accomplish the same task, but with native performance using CPU counters.
​
```
perf stat ./sumtest_sorted
```
​
**Sorted:**
​
```
 Performance counter stats for './sumtest_sorted':
​
  11808.095776 task-clock                #    0.998 CPUs utilized
         1,062 context-switches          #    0.090 K/sec
            14 CPU-migrations            #    0.001 K/sec
           337 page-faults               #    0.029 K/sec
26,487,882,764 cycles                    #    2.243 GHz
41,025,654,322 instructions              #    1.55  insns per cycle
 6,558,871,379 branches                  #  555.455 M/sec
       567,204 branch-misses             #    0.01% of all branches
​
  11.827228330 seconds time elapsed
```
​
**Unsorted:**
​
```
 Performance counter stats for './sumtest_unsorted':
​
  28877.954344 task-clock                #    0.998 CPUs utilized
         2,584 context-switches          #    0.089 K/sec
            18 CPU-migrations            #    0.001 K/sec
           335 page-faults               #    0.012 K/sec
65,076,127,595 cycles                    #    2.253 GHz
41,032,528,741 instructions              #    0.63  insns per cycle
 6,560,579,013 branches                  #  227.183 M/sec
 1,646,394,749 branch-misses             #   25.10% of all branches
​
  28.935500947 seconds time elapsed
```
​
It can also do source code annotation with dissassembly.
​
```
perf record -e branch-misses ./sumtest_unsorted
perf annotate -d sumtest_unsorted
```
​
```
 Percent |      Source code & Disassembly of sumtest_unsorted
------------------------------------------------
...
         :                      sum += data[c];
    0.00 :        400a1a:       mov    -0x14(%rbp),%eax
   39.97 :        400a1d:       mov    %eax,%eax
    5.31 :        400a1f:       mov    -0x20040(%rbp,%rax,4),%eax
    4.60 :        400a26:       cltq
    0.00 :        400a28:       add    %rax,-0x30(%rbp)
...
```
​
See [the performance tutorial](https://perf.wiki.kernel.org/index.php/Tutorial) for more details.
​
### Score: 1632 · By: atlaste · Answered: 2013-04-24
​
I just read up on this question and its answers, and I feel an answer is missing.
​
A common way to eliminate branch prediction that I've found to work particularly good in managed languages is a table lookup instead of using a branch (although I haven't tested it in this case).
​
This approach works in general if:
​
1.  it's a small table and is likely to be cached in the processor, and
2.  you are running things in a quite tight loop and/or the processor can preload the data.
​
**Background and why**
​
From a processor perspective, your memory is slow. To compensate for the difference in speed, a couple of caches are built into your processor (L1/L2 cache). So imagine that you're doing your nice calculations and figure out that you need a piece of memory. The processor will get its 'load' operation and loads the piece of memory into cache -- and then uses the cache to do the rest of the calculations. Because memory is relatively slow, this 'load' will slow down your program.
​
Like branch prediction, this was optimized in the Pentium processors: the processor predicts that it needs to load a piece of data and attempts to load that into the cache before the operation actually hits the cache. As we've already seen, branch prediction sometimes goes horribly wrong -- in the worst case scenario you need to go back and actually wait for a memory load, which will take forever (**in other words: failing branch prediction is bad, a memory load after a branch prediction fail is just horrible!**).
​
Fortunately for us, if the memory access pattern is predictable, the processor will load it in its fast cache and all is well.
​
The first thing we need to know is what is _small_? While smaller is generally better, a rule of thumb is to stick to lookup tables that are <= 4096 bytes in size. As an upper limit: if your lookup table is larger than 64K it's probably worth reconsidering.
​
**Constructing a table**
​
So we've figured out that we can create a small table. Next thing to do is get a lookup function in place. Lookup functions are usually small functions that use a couple of basic integer operations (and, or, xor, shift, add, remove and perhaps multiply). You want to have your input translated by the lookup function to some kind of 'unique key' in your table, which then simply gives you the answer of all the work you wanted it to do.
​
In this case: >= 128 means we can keep the value, < 128 means we get rid of it. The easiest way to do that is by using an 'AND': if we keep it, we AND it with 7FFFFFFF; if we want to get rid of it, we AND it with 0. Notice also that 128 is a power of 2 -- so we can go ahead and make a table of 32768/128 integers and fill it with one zero and a lot of 7FFFFFFFF's.
​
**Managed languages**
​
You might wonder why this works well in managed languages. After all, managed languages check the boundaries of the arrays with a branch to ensure you don't mess up...
​
Well, not exactly... :-)
​
There has been quite some work on eliminating this branch for managed languages. For example:
​
```
for (int i = 0; i < array.Length; ++i)
{
   // Use array[i]
}
```
​
In this case, it's obvious to the compiler that the boundary condition will never be hit. At least the Microsoft JIT compiler (but I expect Java does similar things) will notice this and remove the check altogether. WOW, that means no branch. Similarly, it will deal with other obvious cases.
​
If you run into trouble with lookups in managed languages -- the key is to add a `& 0x[something]FFF` to your lookup function to make the boundary check predictable -- and watch it going faster.
​
**The result of this case**
​
```
// Generate data
int arraySize = 32768;
int[] data = new int[arraySize];
​
Random random = new Random(0);
for (int c = 0; c < arraySize; ++c)
{
    data[c] = random.Next(256);
}
​
/*To keep the spirit of the code intact, I'll make a separate lookup table
(I assume we cannot modify 'data' or the number of loops)*/
​
int[] lookup = new int[256];
​
for (int c = 0; c < 256; ++c)
{
    lookup[c] = (c >= 128) ? c : 0;
}
​
// Test
DateTime startTime = System.DateTime.Now;
long sum = 0;
​
for (int i = 0; i < 100000; ++i)
{
    // Primary loop
    for (int j = 0; j < arraySize; ++j)
    {
        /* Here you basically want to use simple operations - so no
        random branches, but things like &, |, *, -, +, etc. are fine. */
        sum += lookup[data[j]];
    }
}
​
DateTime endTime = System.DateTime.Now;
Console.WriteLine(endTime - startTime);
Console.WriteLine("sum = " + sum);
Console.ReadLine();
```
​
### Score: 1453 · By: Saqlain · Answered: 2013-02-15
​
As data is distributed between 0 and 255 when the array is sorted, around the first half of the iterations will not enter the `if`\-statement (the `if` statement is shared below).
​
```
if (data[c] >= 128)
    sum += data[c];
```
​
The question is: What makes the above statement not execute in certain cases as in case of sorted data? Here comes the "branch predictor". A branch predictor is a digital circuit that tries to guess which way a branch (e.g. an `if-then-else` structure) will go before this is known for sure. The purpose of the branch predictor is to improve the flow in the instruction pipeline. Branch predictors play a critical role in achieving high effective performance!
​
**Let's do some bench marking to understand it better**
​
The performance of an `if`\-statement depends on whether its condition has a predictable pattern. If the condition is always true or always false, the branch prediction logic in the processor will pick up the pattern. On the other hand, if the pattern is unpredictable, the `if`\-statement will be much more expensive.
​
Let’s measure the performance of this loop with different conditions:
​
```
for (int i = 0; i < max; i++)
    if (condition)
        sum++;
```
​
Here are the timings of the loop with different true-false patterns:
​
```
Condition                Pattern             Time (ms)
-------------------------------------------------------
(i & 0×80000000) == 0    T repeated          322
​
(i & 0xffffffff) == 0    F repeated          276
​
(i & 1) == 0             TF alternating      760
​
(i & 3) == 0             TFFFTFFF…           513
​
(i & 2) == 0             TTFFTTFF…           1675
​
(i & 4) == 0             TTTTFFFFTTTTFFFF…   1275
​
(i & 8) == 0             8T 8F 8T 8F …       752
​
(i & 16) == 0            16T 16F 16T 16F …   490
```
​
A “**bad**” true-false pattern can make an `if`\-statement up to six times slower than a “**good**” pattern! Of course, which pattern is good and which is bad depends on the exact instructions generated by the compiler and on the specific processor.
​
So there is no doubt about the impact of branch prediction on performance!
​
### Score: 1389 · By: steveha · Answered: 2013-07-22
​
One way to avoid branch prediction errors is to build a lookup table, and index it using the data. Stefan de Bruijn discussed that in his answer.
​
But in this case, we know values are in the range \[0, 255\] and we only care about values >= 128. That means we can easily extract a single bit that will tell us whether we want a value or not: by shifting the data to the right 7 bits, we are left with a 0 bit or a 1 bit, and we only want to add the value when we have a 1 bit. Let's call this bit the "decision bit".
​
By using the 0/1 value of the decision bit as an index into an array, we can make code that will be equally fast whether the data is sorted or not sorted. Our code will always add a value, but when the decision bit is 0, we will add the value somewhere we don't care about. Here's the code:
​
```
// Test
clock_t start = clock();
long long a[] = {0, 0};
long long sum;
​
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        int j = (data[c] >> 7);
        a[j] += data[c];
    }
}
​
double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
sum = a[1];
```
​
This code wastes half of the adds but never has a branch prediction failure. It's tremendously faster on random data than the version with an actual if statement.
​
But in my testing, an explicit lookup table was slightly faster than this, probably because indexing into a lookup table was slightly faster than bit shifting. This shows how my code sets up and uses the lookup table (unimaginatively called `lut` for "LookUp Table" in the code). Here's the C++ code:
​
```
// Declare and then fill in the lookup table
int lut[256];
for (unsigned c = 0; c < 256; ++c)
    lut[c] = (c >= 128) ? c : 0;
​
// Use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        sum += lut[data[c]];
    }
}
```
​
In this case, the lookup table was only 256 bytes, so it fits nicely in a cache and all was fast. This technique wouldn't work well if the data was 24-bit values and we only wanted half of them... the lookup table would be far too big to be practical. On the other hand, we can combine the two techniques shown above: first shift the bits over, then index a lookup table. For a 24-bit value that we only want the top half value, we could potentially shift the data right by 12 bits, and be left with a 12-bit value for a table index. A 12-bit table index implies a table of 4096 values, which might be practical.
​
The technique of indexing into an array, instead of using an `if` statement, can be used for deciding which pointer to use. I saw a library that implemented binary trees, and instead of having two named pointers (`pLeft` and `pRight` or whatever) had a length-2 array of pointers and used the "decision bit" technique to decide which one to follow. For example, instead of:
​
```
if (x < node->value)
    node = node->pLeft;
else
    node = node->pRight;
```
​
this library would do something like:
​
```
i = (x < node->value);
node = node->link[i];
```
​
Here's a link to this code: [Red Black Trees](https://web.archive.org/web/20190207151651/https://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx), _Eternally Confuzzled_
​
### Score: 1245 · By: user1196549 · Answered: 2013-07-24
​
In the sorted case, you can do better than relying on successful branch prediction or any branchless comparison trick: completely remove the branch.
​
Indeed, the array is partitioned in a contiguous zone with `data < 128` and another with `data >= 128`. So you should find the partition point with a [dichotomic search](https://en.wikipedia.org/wiki/Dichotomic_search) (using `Lg(arraySize) = 15` comparisons), then do a straight accumulation from that point.
​
Something like (unchecked)
​
```
int i= 0, j, k= arraySize;
while (i < k)
{
  j= (i + k) >> 1;
  if (data[j] >= 128)
    k= j;
  else
    i= j;
}
sum= 0;
for (; i < arraySize; i++)
  sum+= data[i];
```
​
or, slightly more obfuscated
​
```
int i, k, j= (i + k) >> 1;
for (i= 0, k= arraySize; i < k; (data[j] >= 128 ? k : i)= j)
  j= (i + k) >> 1;
for (sum= 0; i < arraySize; i++)
  sum+= data[i];
```
​
A yet faster approach, that gives an **approximate** solution for both sorted or unsorted is: `sum= 3137536;` (assuming a truly uniform distribution, 16384 samples with expected value 191.5) **:-)**
​
### Score: 1050 · By: Harsh Sharma · Answered: 2015-07-03
​
The above behavior is happening because of Branch prediction.
​
To understand branch prediction one must first understand an **Instruction Pipeline.**
​
The the steps of running an instruction can be overlapped with the sequence of steps of running the previous and next instruction, so that different steps can be executed concurrently in parallel. This technique is known as instruction pipelining and is used to increase throughput in modern processors. To understand this better please see this [example on Wikipedia](https://en.wikipedia.org/wiki/Pipeline_\(computing\)#Concept_and_motivation).
​
Generally, modern processors have quite long (and wide) pipelines, so many instruction can be in flight. See [Modern Microprocessors A 90-Minute Guide!](https://www.lighterra.com/papers/modernmicroprocessors/) which starts by introducing basic in-order pipelining and goes from there.
​
But for ease **let's consider a simple in-order pipeline with these 4 steps only.**
(Like a [classic 5-stage RISC](https://en.wikipedia.org/wiki/Classic_RISC_pipeline), but omitting a separate MEM stage.)
​
1.  IF -- Fetch the instruction from memory
2.  ID -- Decode the instruction
3.  EX -- Execute the instruction
4.  WB -- Write back to CPU register
​
**4-stage pipeline in general for 2 instructions.**
4-stage pipeline in general
​
Moving back to the above question let's consider the following instructions:
​
```
                        A) if (data[c] >= 128)
                                /\
                               /  \
                              /    \
                        true /      \ false
                            /        \
                           /          \
                          /            \
                         /              \
              B) sum += data[c];          C) for loop or print().
```
​
Without branch prediction, the following would occur:
​
To execute instruction B or instruction C the processor will have to wait (_stall_) till the instruction A leaves the EX stage in the pipeline, as the decision to go to instruction B or instruction C depends on the result of instruction A. (i.e. where to fetch from next.) So the pipeline will look like this:
​
_**Without prediction: when `if` condition is true:**_ enter image description here
​
_**Without prediction: When `if` condition is false:**_ enter image description here
​
As a result of waiting for the result of instruction A, the total CPU cycles spent in the above case (without branch prediction; for both true and false) is 7.
​
**So what is branch prediction?**
​
Branch predictor will try to guess which way a branch (an if-then-else structure) will go before this is known for sure. It will not wait for the instruction A to reach the EX stage of the pipeline, but it will guess the decision and go to that instruction (B or C in case of our example).
​
_**In case of a correct guess, the pipeline looks something like this:**_ enter image description here
​
If it is later detected that the guess was wrong then the partially executed instructions are discarded and the pipeline starts over with the correct branch, incurring a delay. The time that is wasted in case of a branch misprediction is equal to the number of stages in the pipeline from the fetch stage to the execute stage. Modern microprocessors tend to have quite long pipelines so that the misprediction delay is between 10 and 20 clock cycles. The longer the pipeline the greater the need for a good [branch predictor](https://en.wikipedia.org/wiki/Branch_predictor).
​
In the OP's code, the first time when the conditional, the branch predictor does not have any information to base up prediction, so the first time it will randomly choose the next instruction. (Or fall back to _static_ prediction, typically forward not-taken, backward taken). Later in the for loop, it can base the prediction on the history. For an array sorted in ascending order, there are three possibilities:
​
1.  All the elements are less than 128
2.  All the elements are greater than 128
3.  Some starting new elements are less than 128 and later it become greater than 128
​
Let us assume that the predictor will always assume the true branch on the first run.
​
So in the first case, it will always take the true branch since historically all its predictions are correct. In the 2nd case, initially it will predict wrong, but after a few iterations, it will predict correctly. In the 3rd case, it will initially predict correctly till the elements are less than 128. After which it will fail for some time and the correct itself when it sees branch prediction failure in history.
​
In all these cases the failure will be too less in number and as a result, only a few times it will need to discard the partially executed instructions and start over with the correct branch, resulting in fewer CPU cycles.
​
But in case of a random unsorted array, the prediction will need to discard the partially executed instructions and start over with the correct branch most of the time and result in more CPU cycles compared to the sorted array.
​
* * *
​
Further reading:
​
*   [Modern Microprocessors A 90-Minute Guide!](https://www.lighterra.com/papers/modernmicroprocessors/)
*   [Dan Luu's article on branch prediction](https://danluu.com/branch-prediction/) (which covers older branch predictors, not modern IT-TAGE or Perceptron)
*   [https://en.wikipedia.org/wiki/Branch\_predictor](https://en.wikipedia.org/wiki/Branch_predictor)
*   [Branch Prediction and the Performance of Interpreters - Don’t Trust Folklore](https://hal.inria.fr/hal-01100647/document) - 2015 paper showing how well Intel's Haswell does at predicting the indirect branch of a Python interpreter's main loop (historically problematic due to a non-simple pattern), vs. earlier CPUs which didn't use IT-TAGE. (They don't help with this fully random case, though. Still 50% mispredict rate for the if inside the loop on a Skylake CPU when the source is compiled to branch asm.)
*   [Static branch prediction on newer Intel processors](https://xania.org/201602/bpu-part-one) - what CPUs actually do when running a branch instruction that doesn't have a dynamic prediction available. Historically, forward not-taken (like an `if` or `break`), backward taken (like a loop) has been used because it's better than nothing. Laying out code so the fast path / common case minimizes taken branches is good for I-cache density as well as static prediction, so compilers already do that. (That's the [real effect](https://stackoverflow.com/questions/1851299/is-it-possible-to-tell-the-branch-predictor-how-likely-it-is-to-follow-the-branc) of `likely` / `unlikely` hints in C source, not actually hinting the hardware branch prediction in most CPU, except maybe via static prediction.)

markdown
# RegEx match open tags except XHTML self-contained tags
​
Score: 2385 · Views: 4,081,698 · Asked: 2009-11-13 · By: Jeff · Tags: html, regex, xhtml · Answers: 36
​
I need to match all of these opening tags:
​
```
<p>
<a href="foo">
```
​
But not self-closing tags:
​
```
<br />
<hr class="foo" />
```
​
I came up with this and wanted to make sure I've got it right. I am only capturing the `a-z`.
​
```
<([a-z]+) *[^/]*?>
```
​
I believe it says:
​
*   Find a less-than, then
*   Find (and capture) a-z one or more times, then
*   Find zero or more spaces, then
*   Find any character zero or more times, greedy, except `/`, then
*   Find a greater-than
​
Do I have that right? And more importantly, what do you think?
​
## Answers (36)
​
### ✅ Accepted · Score: 4394 · By: bobince · Answered: 2009-11-13
​
You can't parse \[X\]HTML with regex. Because HTML can't be parsed by regex. Regex is not a tool that can be used to correctly parse HTML. As I have answered in HTML-and-regex questions here so many times before, the use of regex will not allow you to consume HTML. Regular expressions are a tool that is insufficiently sophisticated to understand the constructs employed by HTML. HTML is not a regular language and hence cannot be parsed by regular expressions. Regex queries are not equipped to break down HTML into its meaningful parts. so many times but it is not getting to me. Even enhanced irregular regular expressions as used by Perl are not up to the task of parsing HTML. You will never make me crack. HTML is a language of sufficient complexity that it cannot be parsed by regular expressions. Even Jon Skeet cannot parse HTML using regular expressions. Every time you attempt to parse HTML with regular expressions, the unholy child weeps the blood of virgins, and Russian hackers pwn your webapp. Parsing HTML with regex summons tainted souls into the realm of the living. HTML and regex go together like love, marriage, and ritual infanticide. The <center> cannot hold it is too late. The force of regex and HTML together in the same conceptual space will destroy your mind like so much watery putty. If you parse HTML with regex you are giving in to Them and their blasphemous ways which doom us all to inhuman toil for the One whose Name cannot be expressed in the Basic Multilingual Plane, he comes. HTML-plus-regexp will liquify the n​erves of the sentient whilst you observe, your psyche withering in the onslaught of horror. Rege̿̔̉x-based HTML parsers are the cancer that is killing StackOverflow _it is too late it is too late we cannot be saved_ the transgression of a chi͡ld ensures regex will consume all living tissue (except for HTML which it cannot, as previously prophesied) _dear lord help us how can anyone survive this scourge_ using regex to parse HTML has doomed humanity to an eternity of dread torture and security holes _using rege_x as a tool to process HTML establishes a brea_ch between this world_ and the dread realm of c͒ͪo͛ͫrrupt entities (like SGML entities, but _more corrupt) a mere glimp_se of the world of reg​**ex parsers for HTML will ins**​tantly transport a p_rogrammer's consciousness i_nto a w_orl_d of ceaseless screaming, he comes, the pestilent slithy regex-infection wil​**l devour your HT**​ML parser, application and existence for all time like Visual Basic only worse _he comes he com_es _do not fi_​ght h**e com̡e̶s, ̕h̵i**​s un̨ho͞ly radiańcé de_stro҉ying all enli̍̈́̂̈́ghtenment, HTML tags **lea͠ki̧n͘g fr̶ǫm ̡yo​͟ur eye͢s̸ ̛l̕ik͏e liq**​uid p_ain, the song of re̸gular exp​ression parsing will exti_​nguish the voices of mor​**tal man from the sp**​here I can see it can you see ̲͚̖͔̙î̩́t̲͎̩̱͔́̋̀ it is beautiful t​_he f`inal snuf`fing o_f the lie​**s of Man ALL IS LOŚ͖̩͇̗̪̏̈́T A**_**LL I​S L**OST th_e pon̷y he come_s he c̶̮omes he co**mes t_he_ ich​**or permeat_es al_l MY FAC_E MY FACE ᵒh god n**o NO NOO̼**_**O​O N**Θ stop t_he an​\*̶͑̾̾​̅ͫ͏̙̤g͇̫͛͆̾ͫ̑͆l͖͉̗̩̳̟̍ͫͥͨ_e̠̅s `͎a̧͈͖r̽̾̈́͒͑e` n**​ot rè̑ͧ̌aͨl̘̝̙̃ͤ͂̾̆ ZA̡͊͠͝LGΌ ISͮ̂҉̯͈͕̹̘̱ T**O͇̹̺ͅƝ̴ȳ̳ TH̘**Ë͖́̉ ͠P̯͍̭O̚​N̐Y̡ H̸̡̪̯ͨ͊̽̅̾̎Ȩ̬̩̾͛ͪ̈́̀́͘ ̶̧̨̱̹̭̯ͧ̾ͬC̷̙̲̝͖ͭ̏ͥͮ͟Oͮ͏̮̪̝͍M̲̖͊̒ͪͩͬ̚̚͜Ȇ̴̟̟͙̞ͩ͌͝**S̨̥̫͎̭ͯ̿̔̀ͅ
​
* * *
​
Have you tried using an XML parser instead?
​
* * *
​
> **Moderator's Note**
>
> This post is locked to prevent inappropriate edits to its content. The post looks exactly as it is supposed to look - there are no problems with its content. Please do not flag it for our attention.
​
### Score: 3624 · By: Kaitlin Duck Sherwood · Answered: 2009-11-14
​
While parsing _arbitrary_ HTML with only a regex is impossible, it's sometimes appropriate to use them for parsing a _limited, known_ set of HTML.
​
If you have a small set of HTML pages that you want to scrape data from and then stuff into a database, regexes might work fine. For example, I recently wanted to get the names, parties, and districts of Australian federal Representatives, which I got off of the Parliament's web site. This was a limited, one-time job.
​
Regexes worked just fine for me, and were very fast to set up.
​
### Score: 2404 · By: NealB · Answered: 2009-11-18
​
I think the flaw here is that HTML is a [Chomsky Type 2 grammar (context free grammar)](http://en.wikipedia.org/wiki/Context-free_grammar) and a regular expression is a [Chomsky Type 3 grammar (regular grammar)](http://en.wikipedia.org/wiki/Regular_grammar). Since a Type 2 grammar is fundamentally more complex than a Type 3 grammar (see the [Chomsky hierarchy](http://en.wikipedia.org/wiki/Chomsky_hierarchy)), you can't possibly make this work.
​
But many will try, and some will even claim success, but that is until others find the fault and will totally mess you up.
​
### Score: 1199 · By: itsadok · Answered: 2009-11-15
​
**Disclaimer**: Use a parser if you have the option. That said...
​
This is the regex I use (!) to match HTML tags:
​
```
<(?:"[^"]*"['"]*|'[^']*'['"]*|[^'">])+>
```
​
It may not be perfect, but I ran this code through a _lot_ of HTML. Note that it even catches strange things like `<a name="badgenerator"">`, which show up on the web.
​
I guess to make it not match self-contained tags, you'd either want to use [Kobi's](https://stackoverflow.com/questions/1732348/regex-match-open-tags-except-xhtml-self-contained-tags/1732395#1732395) negative look-behind:
​
```
<(?:"[^"]*"['"]*|'[^']*'['"]*|[^'">])+(?<!/\s*)>
```
​
Or just combine if and if not.
​
**To downvoters:** This is working code from an actual product. I doubt anyone reading this page will get the impression that it is socially acceptable to use regexes on HTML content.
​
**Caveat**: I should note that this regex still breaks down in the presence of [CDATA](https://en.wikipedia.org/wiki/CDATA) blocks, comments, and script and style elements. The good news is that you can get rid of those using a regex...
​
### Score: 613 · By: xanatos · Answered: 2011-03-08
​
There are people that will tell you that the Earth is round (or perhaps that the Earth is an oblate spheroid if they want to use strange words). They are lying.
​
There are people that will tell you that Regular expressions shouldn't be recursive. They are limiting you. They need to subjugate you, and they do it by keeping you in ignorance.
​
You can live in their reality or take the red pill.
​
Like Lord Marshal (is he a relative of the Marshal .NET class?), I have seen the Underverse Stack Based Regex-Verse and returned with powers knowledge you can't imagine. Yes, I think there were an Old One or two protecting them, but they were watching football on the TV, so it wasn't difficult.
​
I think the XML case is quite simple. The RegEx (in the .NET syntax), deflated and coded in [Base64](https://en.wikipedia.org/wiki/Base64) to make it easier to comprehend by your feeble mind, should be something like this:
​
```
7L0HYBxJliUmL23Ke39K9UrX4HShCIBgEyTYkEAQ7MGIzeaS7B1pRyMpqyqBymVWZV1mFkDM7Z28
995777333nvvvfe6O51OJ/ff/z9cZmQBbPbOStrJniGAqsgfP358Hz8itn6Po9/3eIue3+Px7/3F
86enJ8+/fHn64ujx7/t7vFuUd/Dx65fHJ6dHW9/7fd/t7fy+73Ye0v+f0v+Pv//JnTvureM3b169
OP7i9Ogyr5uiWt746u+BBqc/8dXx86PP7tzU9mfQ9tWrL18d3UGnW/z7nZ9htH/y9NXrsy9fvPjq
i5/46ss3p4z+x3e8b452f9/x93a2HxIkH44PpgeFyPD6lMAEHUdbcn8ffTP9fdTrz/8rBPCe05Iv
p9WsWF788Obl9MXJl0/PXnwONLozY747+t7x9k9l2z/4vv4kqo1//993+/vf2kC5HtwNcxXH4aOf
LRw2z9/v8WEz2LTZcpaV1TL/4c3h66ex2Xv95vjF0+PnX744PbrOm59ZVhso5UHYME/dfj768H7e
Yy5uQUydDAH9+/4eR11wHbqdfPnFF6cv3ogq/V23t++4z4620A13cSzd7O1s/77rpw+ePft916c7
O/jj2bNnT7e/t/397//M9+ibA/7s6ZNnz76PP0/kT2rz/Ts/s/0NArvziYxVEZWxbm93xsrUfnlm
rASN7Hf93u/97vvf+2Lx/e89L7+/FSXiz4Bkd/hF5mVq9Yik7fcncft9350QCu+efkr/P6BfntEv
z+iX9c4eBrFz7wEwpB9P+d9n9MfuM3yzt7Nzss0/nuJfbra3e4BvZFR7z07pj3s7O7uWJM8eCkme
nuCPp88MfW6kDeH7+26PSTX8vu+ePAAiO4LVp4zIPWC1t7O/8/+pMX3rzo2KhL7+8s23T1/RhP0e
vyvm8HbsdmPXYDVhtpdnAzJ1k1jeufOtUAM8ffP06Zcnb36fl6dPXh2f/F6nRvruyHfMd9rgJp0Y
gvsRx/6/ZUzfCtX4e5hTndGzp5jQo9e/z+s3p1/czAUMlts+P3tz+uo4tISd745uJxvb3/v4ZlWs
mrjfd9SG/swGPD/6+nh+9MF4brTBRmh1Tl5+9eT52ckt5oR0xldPzp7GR8pfuXf5PWJv4nJIwvbH
W3c+GY3vPvrs9zj8Xb/147/n7/b7/+52DD2gsSH8zGDvH9+i9/fu/PftTfTXYf5hB+9H7P1BeG52
MTtu4S2cTAjDizevv3ry+vSNb8N+3+/1po2anj4/hZsGt3TY4GmjYbEKDJ62/pHB+3/LmL62wdsU
1J18+eINzTJr3dMvXr75fX7m+MXvY9XxF2e/9+nTgPu2bgwh5U0f7u/74y9Pnh6/OX4PlA2UlwTn
xenJG8L996VhbP3++PCrV68QkrjveITxr2TIt+lL+f3k22fPn/6I6f/fMqZvqXN/K4Xps6sazUGZ
GeQlar49xEvajzI35VRevDl78/sc/b7f6jkG8Va/x52N4L9lBe/kZSh1hr9fPj19+ebbR4AifyuY
12efv5CgGh9TroR6Pj2l748iYxYgN8Z7pr0HzRLg66FnRvcjUft/45i+pRP08vTV6TOe2N/9jv37
R9P0/5YxbXQDeK5E9R12XdDA/4zop+/9Ht/65PtsDVlBBUqko986WsDoWqvbPD2gH/T01DAC1NVn
3/uZ0feZ+T77fd/GVMkA4KjeMcg6RcvQLRl8HyPaWVStdv17PwHV0bOB9xUh7rfMp5Zu3icBJp25
D6f0NhayHyfI3HXHY6YYCw7Pz17fEFhQKzS6ZWChrX+kUf7fMqavHViEPPKjCf1/y5hukcyPTvjP
mHQCppRDN4nbVFPaT8+ekpV5/TP8g/79mVPo77PT1/LL7/MzL7548+XvdfritflFY00fxIsvSQPS
mvctdYZpbt7vxKRfj3018OvC/hEf/79lTBvM3debWj+b8KO0wP+3OeM2aYHumuCAGonmCrxw9cVX
X1C2d4P+uSU7eoBUMzI3/f9udjbYl/el04dI7s8fan8dWRjm6gFx+NrKeFP+WX0CxBdPT58df/X8
DaWLX53+xFdnr06f/szv++NnX7x8fnb6NAhIwsbPkPS7iSUQAFETvP2Tx8+/Og0Xt/yBvDn9vd/c
etno8S+81QKXptq/ffzKZFZ+4e/743e8zxino+8RX37/k595h5/H28+y7fPv490hQdJ349E+txB3
zPZ5J/jsR8bs/y1j2hh/2fkayOqEmYcej0cXUWMN7QrqBwjDrVZRfyQM3xjj/EgYvo4wfLTZrnVS
ebdKq0XSZJvzajKQDUv1/P3NwbEP7cN5+Odivv9/ysPfhHfkOP6b9Fl+91v7LD9aCvp/+Zi+7lLQ
j0zwNzYFP+/Y6r1NcFeDbfBIo8rug3zS3/3WPumPlN3/y8f0I2X3cz4FP+/Y6htSdr2I42fEuSPX
/ewpL4e9/n1evzn94hb+Plpw2+dnbyh79zx0CsPvbq0lb+UQ/h7xvqPq/Gc24PnR18fzVrp8I57d
mehj7ebk5VdPnp+d3GJOSP189eTsaXyk/JV7l98j4SAZgRxtf7x155PR+O6jz36Pw9/1Wz/+e/5u
v//vbsfQAxobws8M9v7xLXp/785/395ED4nO1wx5fsTeH4LnRva+eYY8rpZUBFb/j/jfm8XAvfEj
4/b/ljF1F9B/jx5PhAkp1nu/+y3n+kdZp/93jWmjJ/M11TG++VEG6puZn593PPejoOyHMQU/79jq
GwrKfpSB+tmcwZ93XPkjZffDmIKfd2z1DSm7bmCoPPmjBNT74XkrVf71I/Sf6wTU7XJA4RB+lIC6
mW1+xN5GWw1/683C5rnj/m364cmr45Pf6/SN9H4Us4LISn355vjN2ZcvtDGT6fHvapJcMISmxc0K
MAD4IyP6/5Yx/SwkP360FvD1VTH191mURr/HUY+2P3I9boPnz7Ju/pHrcWPnP3I9/r/L3sN0v52z
0fEgNrgbL8/Evfh9fw/q5Xf93u/97vvf+2Lx/e89L7+/Fe3iZ37f34P5h178kTfx/5YxfUs8vY26
7/d4/OWbb5++ogn7PX5XzOHtOP3GrsHmqobOVO/8Hh1Gk/TPl198QS6w+rLb23fcZ0fMaTfjsv29
7Zul7me2v0FgRoYVURnf9nZEkDD+H2VDf8hjeq8xff1s6GbButNLacEtefHm9VdPXp++CRTw7/v9
r6vW8b9eJ0+/PIHzs1HHdyKE/x9L4Y+s2f+PJPX/1dbsJn3wrY6wiqv85vjVm9Pnp+DgN8efM5va
j794+eb36Xz3mAf5+58+f3r68s230dRvJcxKn/l//oh3f+7H9K2O0r05PXf85s2rH83f/1vGdAvd
w+qBFqsoWvzspozD77EpXYeZ7yzdfxy0ec+l+8e/8FbR84+Wd78xbvn/qQQMz/J7L++GPB7N0MQa
2vTMBwjDrVI0PxKGb4xxfiQMX0cYPuq/Fbx2C1sU8yEF+F34iNsx1xOGa9t6l/yX70uqmxu+qBGm
AxlxWwVS11O97ULqlsFIUvUnT4/fHIuL//3f9/t9J39Y9m8W/Tuc296yUeX/b0PiHwUeP1801Y8C
j/9vz9+PAo8f+Vq35Jb/n0rAz7Kv9aPA40fC8P+RMf3sC8PP08DjR1L3DXHoj6SuIz/CCghZNZb8
fb/Hf/2+37tjvuBY9vu3jmRvxNeGgQAuaAF6Pwj8/+e66M8/7rwpRNj6uVwXZRl52k0n3FVl95Q+
+fz0KSu73/dtkGDYdvZgSP5uskadrtViRKyal2IKAiQfiW+FI+tET/9/Txj9SFf8SFf8rOuKzagx
+r/vD34mUADO1P4/AQAA//8=
```
​
The options to set is `RegexOptions.ExplicitCapture`. The capture group you are looking for is `ELEMENTNAME`. If the capture group `ERROR` is not empty then there was a parsing error and the Regex stopped.
​
If you have problems reconverting it to a human-readable regex, this should help:
​
```
static string FromBase64(string str)
{
    byte[] byteArray = Convert.FromBase64String(str);
​
    using (var msIn = new MemoryStream(byteArray))
    using (var msOut = new MemoryStream()) {
        using (var ds = new DeflateStream(msIn, CompressionMode.Decompress)) {
            ds.CopyTo(msOut);
        }
​
        return Encoding.UTF8.GetString(msOut.ToArray());
    }
}
```
​
If you are unsure, no, I'm _not_ kidding (but perhaps I'm lying). It _will_ work. I've built tons of unit tests to test it, and I have even used (part of) the [conformance tests](http://www.w3.org/XML/Test/). It's a tokenizer, not a full-blown parser, so it will only split the XML into its component tokens. It won't parse/integrate [DTDs](https://en.wikipedia.org/wiki/Document_type_definition).
​
Oh... if you want the source code of the regex, with some auxiliary methods:
​
[Regex to tokenize an XML string](http://pastebin.com/hzYazFVb) or [the full plain regex](https://topaz.github.io/paste/#XQAAAQD5hQAAAAAAAAAUD8Q6Ijb26igjgaUO/S4VLr/Od1fatGY8ycZ79EV23K5OCMWdbg2gH+s7o5uxCPlMSN1JtgtVM2MKR6CqK1eEDhtb5JZyw5spb/FtqvAc3ed4JkSFjzVZF7RTA0u9sRtmbSyVgOdqUpqnibi1CDqHGXGOzOlBKLxSopincGbR0sbzm+mA3nrgLtwe1kqAj3MWoPyOrU8e7ipjvkI+e0LALD6uam6dq+hXtGQJ8LYSeoUpKjGW3LDV7Oh3mE3OBu9AaQF7PiSsUTC2b/AqI1rEOqBWwwkUevXnMnpPYZ+FlYhJ4zgvOyR3YStbExN6Q8h79n9w8lEqI1rr4B2xDaqTgsFd+rg0Iu3S3aaRhII9wdUaipKiEKuDujWemedqT6P+ohRi9CC/lGr8Kz5+QlErsB/97LiffPcTizNflkF8TnInJba8R0w9nhL70OX9IijnRbrHYLnEK62mliz7JFFmSWu9KqzbyrC+OkAQIi0hdmLzITt7lz8OCUKWocUyBeP3JSgXOGX/P8sw3WF6q6QBu0XmN4EgtHfcBb130ewOQ34MhCEw8q79ycePiduoP7MlbzbG5Iw8202AlrfjFp96dawcaALWOIMDGEaM7X1ZC5RFAfcpHNLu/KxctKOoyhIzYWS+LTMMPBx13L4IYXiDysJuG4acbJiDiKfla4i8Z0QGrPLvF7/1A5ufy7yLck9adE1aXZUD7yxX6qXICx+Ue6Fq+PHDslFeU6Q74LWjj/tu8CGM55EMItBrpz5EcTgeoBxNuA/vrYi/Ybm7hMscw/pYGL9RG5H+ok3OzKrWdjintjxvVV+cGNWsN/LNWC3bGp5OJaArP5OCehsMwcAQMQkNi8cpSX+cP6nRaV5nO/5borKcXufMdw8g1zmgTqul+0qISwn3MNK/Y0Qd+KgBIumvIUQT1HzLpbehbjAkYFg+PBUr4BPDAGiEN+lvtSsn3R3yFMyX0TcYe0a5dSBSMpq4P/ZCRJy+2pFLvtIMYJwph34zhLPJOoFK0LiiT+Vgt4yjHLQwGfzSug2oT5TaUAFwOWY2SeTxb5SfaxTB+DX8B+jhlX2DvEVV/EUWcoEkImMx1v9u+yuIshY69ikFaZfcrcCFPRLu6RVog+sLNgXuk/Q+OnoUuoeok367pwuiw26/byFpSFogS2DIRIG2J3agwqa0XPtcHY2j3H2niOigKaOX1oeansYqIjvGykcysm43IhAR2QEcoPKZOhi1bwSwpP98hpin+dkVJDD8f0w/ipDIMpIDRTv45VQWAzdK4yLqaauZRR76QeiAi618bOSiO0LnUYcbyRsU32v9UJ5LMZjzKo/trYrBgY/F4rZG6X+GSl03MbbQM3CHqo1iNc9voknMrNfmuSb7eGB2sNN/B5l0fk57pspZsJ2EuE1v5NtBjwrS9qMQzehoE7sh5YxbNyj9x44FSZDbV/2PXhAgkVZ63td5m8AfPngjAReF4bTvL/rlIWMCbJL6IQKAt2jH4l4wpfFm0qssBl2vdsfNXPhTzRWbB+UPJmxUBGv8YF0rd4Ol3SpuF8fF368DUP96pt96T8W56LIhPULh6yECYWX83QwMyoEvkcgeEJIEm08InYo7UWKRiQml0BTb+YOcy+V20V+k+YAZM2hEjbTNNnXqCvtmVytw1fA6OESzlpcOWzmFwKqwhRAtRJ+Z/YhQLhC7J1xdbFc3cG9hihArqtMRXCCFLcf24zl5rhtV9NJRZdn56s2qspoMtk8m+vGXaLFKdt3j8O5KEaPCILeUbXLS6gtm+ByiGuIF4GWAWcstCh0IQ5j+0J/+5SRp27y/Q0kvZNhD/HrqNmONDE6h7qaE6fKrhrmCLo8XcM59eiEeJuO/KWSDVbpwaDhrx+DS0ngI5TeWmAliRXYUISI/B+hhjFwawuXlK1FAm0Ohyf6XBo4dwoU/SYOHva8wB2qiPlVCvRvs7vK9FkWQjzNw0v/sDHy+nd49LiIdJkvBPsYS72H/E7kLt7P7WVJgpENY4AqXXGtZ6/L5lcByXgFxDgZbiWMKf1GCfb5QNLauPHZBjxI45JvZsDlG3sUaHwnRyYLiDE+ly+w53l2GgVX4wpPQ1JPjCIvLJ8fmKy4B5HOC5uJYTfUyjAeKP5aIloVVGESb8SGbXRfcme11BZmPyBvjivWZ8kABDh6aKGZdUZCvMnlbZnwKYUWl1ZSFi5AMlw0nEu9pFy5h/AIE+yRTioJ9VYn7ZC4njk5p7V7g+ynr8xGDRAcwLQPVUuCVCDVDSx1eGfWa6IT9G6aVHA1+SHx+sPvHNmWCMYpYWPY5b6l5DYXlTPqChQBwMxcGQnusdNEsEvQYV4FBJhYjgLMxfjBoLPPvysNmpg+qItxnBaDZgMEFa4I3Ek1e7f412UaMloHzTKuzotNQE3quvOH0/9zORWQ=)
​
### Score: 329 · By: dubiousjim · Answered: 2010-02-15
​
In a [shell](https://en.wikipedia.org/wiki/Shell_\(computing\)), you can parse [HTML](https://en.wikipedia.org/wiki/HTML) using [sed](https://en.wikipedia.org/wiki/Sed):
​
1.  [Turing.sed](http://sed.sourceforge.net/grabbag/scripts/turing.sed)
2.  Write an HTML parser (homework)
3.  ???
4.  Profit!
​
* * *
​
Related (why you shouldn't use regex match):
​
*   [If You Like Regular Expressions So Much, Why Don't You Marry Them?](https://blog.codinghorror.com/if-you-like-regular-expressions-so-much-why-dont-you-marry-them/)
*   [Regular Expressions: Now You Have Two Problems](https://blog.codinghorror.com/regular-expressions-now-you-have-two-problems/)
*   [Hacking stackoverflow.com's HTML sanitizer](http://danlec.com/blog/hacking-stackoverflow-com-s-html-sanitizer)
​
### Score: 299 · By: Sam · Answered: 2011-09-27
​
I agree that the right tool to parse XML and _especially HTML_ is a parser and not a regular expression engine. However, like others have pointed out, sometimes using a regex is quicker, easier, and gets the job done if you know the data format.
​
Microsoft actually has a section of [Best Practices for Regular Expressions in the .NET Framework](https://learn.microsoft.com/dotnet/standard/base-types/best-practices) and specifically talks about [Consider\[ing\] the Input Source](https://learn.microsoft.com/dotnet/standard/base-types/best-practices#consider-the-input-source).
​
Regular expressions do have limitations, but have you considered the following?
​
The .NET framework is unique when it comes to regular expressions in that it supports [Balancing Group Definitions](https://learn.microsoft.com/dotnet/standard/base-types/grouping-constructs-in-regular-expressions#balancing_group_definition).
​
*   See [Matching Balanced Constructs with .NET Regular Expressions](https://weblogs.asp.net/whaggard/377025)
*   See [.NET Regular Expressions: Regex and Balanced Matching](https://learn.microsoft.com/archive/blogs/bclteam/net-regular-expressions-regex-and-balanced-matching-ryan-byington)
*   See Microsoft's docs on [Balancing Group Definitions](https://learn.microsoft.com/dotnet/standard/base-types/grouping-constructs-in-regular-expressions#balancing_group_definition)
​
For this reason, I believe you _can_ parse XML using regular expressions. Note, however, that it **must be valid XML** (_browsers are very forgiving of HTML and allow bad XML syntax inside HTML_). This is possible since the "Balancing Group Definition" will allow the regular expression engine to act as a [PDA](https://en.wikipedia.org/wiki/Pushdown_automaton).
​
Quote from the first article cited above:
​
> **.NET Regular Expression Engine**
>
> As described above properly balanced constructs cannot be described by a regular expression. However, the .NET regular expression engine provides a few constructs that allow balanced constructs to be recognized.
>
> *   `(?<group>)` - pushes the captured result on the capture stack with the name group.
> *   `(?<-group>)` - pops the top most capture with the name group off the capture stack.
> *   `(?(group)yes|no)` - matches the yes part if there exists a group with the name group otherwise matches no part.
>
> These constructs allow for a .NET regular expression to emulate a restricted PDA by essentially allowing simple versions of the stack operations: push, pop and empty. The simple operations are pretty much equivalent to increment, decrement and compare to zero respectively. This allows for the .NET regular expression engine to recognize a subset of the context-free languages, in particular the ones that only require a simple counter. This in turn allows for the non-traditional .NET regular expressions to recognize individual properly balanced constructs.
​
Consider the following regular expression:
​
```
(?=<ul\s+id="matchMe"\s+type="square"\s*>)
(?>
   <!-- .*? -->                  |
   <[^>]*/>                      |
   (?<opentag><(?!/)[^>]*[^/]>)  |
   (?<-opentag></[^>]*[^/]>)     |
   [^<>]*
)*
(?(opentag)(?!))
```
​
Use the flags:
​
*   Singleline
*   IgnorePatternWhitespace (not necessary if you collapse regex and remove all whitespace)
*   IgnoreCase (not necessary)
​
## Regular Expression Explained (inline)
​
```
(?=<ul\s+id="matchMe"\s+type="square"\s*>) # Match start with <ul id="matchMe"...
(?>                                        # Atomic group / don't backtrack (faster)
   <!-- .*? -->                 |          # Match XML / HTML comment
   <[^>]*/>                     |          # Self closing tag
   (?<opentag><(?!/)[^>]*[^/]>) |          # Push opening XML tag
   (?<-opentag></[^>]*[^/]>)    |          # Pop closing XML tag
   [^<>]*                                  # Something between tags
)*                                         # Match as many XML tags as possible
(?(opentag)(?!))                           # Ensure no 'opentag' groups are on stack
```
​
You can try this at [A Better .NET Regular Expression Tester](http://derekslager.com/blog/posts/2007/09/a-better-dotnet-regular-expression-tester.ashx).
​
I used the sample source of:
​
```
<html>
<body>
<div>
   <br />
   <ul id="matchMe" type="square">
      <li>stuff...</li>
      <li>more stuff</li>
      <li>
          <div>
               <span>still more</span>
               <ul>
                    <li>Another &gt;ul&lt;, oh my!</li>
                    <li>...</li>
               </ul>
          </div>
      </li>
   </ul>
</div>
</body>
</html>
```
​
This found the match:
​
```
   <ul id="matchMe" type="square">
      <li>stuff...</li>
      <li>more stuff</li>
      <li>
          <div>
               <span>still more</span>
               <ul>
                    <li>Another &gt;ul&lt;, oh my!</li>
                    <li>...</li>
               </ul>
          </div>
      </li>
   </ul>
```
​
Although it actually came out like this:
​
```
<ul id="matchMe" type="square">           <li>stuff...</li>           <li>more stuff</li>           <li>               <div>                    <span>still more</span>                    <ul>                         <li>Another &gt;ul&lt;, oh my!</li>                         <li>...</li>                    </ul>               </div>           </li>        </ul>
```
​
Lastly, I really enjoyed Jeff Atwood's article: [Parsing HTML The Cthulhu Way](https://blog.codinghorror.com/parsing-html-the-cthulhu-way/). Funny enough, it cites the answer to this question that currently has over 4k votes.
​
### Score: 271 · By: John Fiala · Answered: 2009-11-13
​
I suggest using [QueryPath](http://querypath.org/) for parsing XML and HTML in PHP. It's basically much the same syntax as jQuery, only it's on the server side.
​
### Score: 244 · By: moritz · Answered: 2010-01-27
​
While the answers that you can't parse HTML with regexes are correct, they don't apply here. The OP just wants to parse one HTML tag with regexes, and that is something that can be done with a regular expression.
​
The suggested regex is wrong, though:
​
```
<([a-z]+) *[^/]*?>
```
​
If you add something to the regex, by backtracking it can be forced to match silly things like `<a >>`, `[^/]` is too permissive. Also note that `<space>*[^/]*` is redundant, because the `[^/]*` can also match spaces.
​
My suggestion would be
​
```
<([a-z]+)[^>]*(?<!/)>
```
​
Where `(?<! ... )` is (in Perl regexes) the negative look-behind. It reads "a <, then a word, then anything that's not a >, the last of which may not be a /, followed by >".
​
Note that this allows things like `<a/ >` (just like the original regex), so if you want something more restrictive, you need to build a regex to match attribute pairs separated by spaces.
​
### Score: 206 · By: cytinus · Answered: 2012-05-17
​
[Sun Tzu](https://en.wikipedia.org/wiki/Sun_Tzu), an ancient Chinese strategist, general, and philosopher, said:
​
> It is said that if you know your enemies and know yourself, you can win a hundred battles without a single loss. If you only know yourself, but not your opponent, you may win or may lose. If you know neither yourself nor your enemy, you will always endanger yourself.
​
In this case, your enemy is HTML and you are either yourself or regex. You might even be Perl with irregular regex. Know HTML. Know yourself.
​
I have composed a haiku describing the nature of HTML.
​
```
HTML has
complexity exceeding
regular language.
```
​
I have also composed a haiku describing the nature of regex in Perl.
​
```
The regex you seek
is defined within the phrase
<([a-zA-Z]+)(?:[^>]*[^/]*)?>
```

markdown
# What Does it Really Mean to Have Different Kinds of Infinities?
​
Score: 203 · Views: 15,315 · Asked: 2010-07-20 · By: Allain Lalonde · Tags: elementary-set-theory, intuition, infinity, faq · Answers: 9
​
Can someone explain to me how there can be different kinds of infinities?
​
I was reading "[The man who loved only numbers](http://en.wikipedia.org/wiki/The_Man_Who_Loved_Only_Numbers)" by [Paul Hoffman](http://en.wikipedia.org/wiki/Paul_Hoffman_\(science_writer\)) and came across the concept of countable and uncountable infinities, but they're only words to me.
​
Any help would be appreciated.
​
## Answers (9)
​
### ✅ Accepted · Score: 212 · By: Noah Snyder · Answered: 2010-07-20
​
Suppose no one ever taught you the names for ordinary numbers. Then suppose that you and I agreed that we would trade one bushel of corn for each of my sheep. But there's a problem, we don't know how to count the bushels or the sheep! So what do we do?
​
We form a "bijection" between the two sets. That's just fancy language for saying you pair things up by putting one bushel next to each of the sheep. When we're done we swap. We've just proved that the number of sheep is the same as the number of bushels without actually counting.
​
We can try doing the same thing with infinite sets. So suppose you have the set of positive integers and I have the set of rational numbers and you want to trade me one positive integer for each of my rationals. Can you do so in a way that gets all of my rational numbers?
​
Perhaps surprisingly the answer is yes! You make the rational numbers into a big square grid with the numerator and denominators as the two coordinates. Then you start placing your "bushels" along diagonals of increasing size, [see wikipedia](http://en.wikipedia.org/wiki/File:Pairing_natural.svg).
​
This says that the rational numbers are "countable" that is you can find a clever way to count them off in the above fashion.
​
The remarkable fact is that for the real numbers there's _no way at all_ to count them off in this way. No matter how clever you are you won't be able to scam me out of all of my real numbers by placing a natural number next to each of them. The proof of that is Cantor's clever "[diagonal argument](http://en.wikipedia.org/wiki/Cantor's_diagonal_argument)."
​
### Score: 27 · By: FordBuchanan · Answered: 2010-07-20
​
[Hilbert's Hotel](http://en.wikipedia.org/wiki/Hilbert%27s_paradox_of_the_Grand_Hotel) is a classic demonstration.
​
### Score: 25 · By: user1119 · Answered: 2010-08-14
​
> How there can be different kinds of infinities?
​
This is very simple to see. This is because of:
​
**Claim:** A given set $X$ and its power set $\\mathcal{P}(X)$ can never be in bijection.
​
**Proof:** By contradiction. Let $f$ be any function from $X$ to $\\mathcal{P}(X)$. It suffices to prove $f$ cannot be surjective. That means that some member of $\\mathcal{P}(X)$, i.e. some subset of $X$, is not in the image of $f$. Consider the set:$$T=\\{x\\in X:x\\not \\in f(x)\\}.$$For every $x$ in $X$, either $x$ is in $T$ or it is not. If $x$ is in $T$, then by definition of $T$, $x$ is not in $f(x)$, so the set $T$ can not be the set $f(x)$ (because $x\\in T$ but $x\\not \\in f(x)$). On the other hand, if $x$ is not in $T$, then by definition of $T$, $x$ is in $f(x)$, so again the set $T$ can not be the set $f(x)$. We just proved that $T$ is NOT $f(x)$ for any $x$, and so $f$ is not surjective. $\\mathsf{QED}$
​
Thus take any infinite set you like. Then take its power set, its power set, and so on. You get an infinite sequence of sets of increasing cardinality (here I am skipping a little; but a use of the Cantor-Schröder-Bernstein theorem will fix things).
​
### Score: 19 · By: François G. Dorais · Answered: 2010-07-20
​
> A _countably infinite_ set is a set for which you can list the elements: $a\_1,a\_2,a\_3,\\ldots$.
​
For example, the set of all integers is countably infinite since I can list its elements as follows:$$0,1,-1,2,-2,3,-3,\\ldots .$$So is the set of rational numbers, but this is more difficult to see. Let's start with the positive rationals. Can you see the pattern in this listing?$$\\frac{1}{1},\\frac{1}{2},\\frac{2}{1},\\frac{1}{3},\\frac{2}{2},\\frac{3}{1},\\frac{1}{4},\\frac{2}{3},\\frac{3}{2},\\frac{4}{1},\\frac{1}{5},\\frac{2}{4},\\ldots .$$(Hint: Add the numerator and denominator to see a different pattern.)
​
This listing has lots of repeats, e.g. $\\dfrac{1}{1}=\\dfrac{2}{2}$ and $\\dfrac{1}{2}=\\dfrac{2}{4}$. That's ok since I can condense the listing by skipping over any repeats.$$\\frac{1}{1},\\frac{1}{2},\\frac{2}{1},\\frac{1}{3},\\frac{3}{1},\\frac{1}{4},\\frac{2}{3},\\frac{3}{2},\\frac{4}{1},\\frac{1}{5},\\ldots .$$Let's write $q\_n$ for the $n$\-th element of this list. Then $0,q\_1,-q\_1,q\_2,-q\_2,q\_3,-q\_3,\\ldots$ is a listing of all rational numbers.
​
> A _countable set_ is a set which is either finite or countably infinite; an _uncountable set_ is a set which is not countable.
​
Thus, an uncountable set is an infinite set which has no listing of all of its elements (as in the definition of countably infinite set).
​
An example of an uncountable set is the set of all real numbers. To see this, you can use the _diagonal method_. Ask another question to see how this works.
​
### Score: 13 · By: workmad3 · Answered: 2010-07-20
​
The basic concept is thus:
​
*   A 'countable' infinity is one where you can give each item in the set an integer and 'count' them (even though there are an infinite number of them)
*   An 'uncountable' infinity defies this. You cannot assign an integer to each item in the set because you will miss items.
​
The key to seeing this is using the 'diagonal slash' argument as originally put forward by Cantor. With a countable infinity, you can create a list of all the items in the set and assign each one a different natural number. This can be done with the naturals (obviously) and the complete range of integers (including negative numbers) and even the rational numbers (so including fractions). It cannot be done with the reals due to the diagonal slash argument:
​
1.  Create your list of all real numbers and assign each one an integer
2.  Create a real number with the rule that the first digit after the decimal point is different from the first digit of your first number, the second digit is different from the second digit of your second number, and so on for all digits
3.  Try and place this number in your list of all numbers... it can't be the first number, or the second or the third... and so on down the list.
4.  Reductio Ad Absurdium, your number does not exist in your countable list of all real numbers and must be added on to create a new list. The same process can then be done again to show the list still isn't complete.
​
This shows a difference between two obviously infinite sets and leads to the somewhat scary conclusion that there are (at least) 2 different forms of infinity.
​
### Score: 13 · By: Jonathan Fischoff · Answered: 2010-07-22
​
Infinity is an overloaded term that can mean many things.
​
One common non-mathematical use of infinity is to refer to everything in the universe. This is **not** what mathematicians mean when they say infinity. That would be a kin to the set of all sets, which is a paradoxical concept that is not part of mathematical discourse.
​
Mathematicians will use infinity as a way to represent a process that continues indefinitely. This is a kin to saying "take the limit as n goes to infinity", which is close to saying "continue this process indefinitely."
​
Infinity is also use infinity to talk about size. All sets are either infinite or finite.
​
The story doesn't stop there. There is something fundamentally different about sets like the points on a line, where there are no holes, and sets like the integers where there are holes. They are both infinite but one seems denser then the other.
​
That's where whole countable uncountable thing comes in. Infinite sets have a size, but it is not a number in the traditional sense. Its more like "relative size". Bijections are how we determine size for infinite sets, which are explained well on this page, so I won't repeat the explanation.
​
A more in-depth, but still understandable explanation is given in Computability and Logic by George Boolos.
​
### Score: 11 · By: Bruno Loff · Answered: 2010-07-20
​
You can see that there are infinitely many natural numbers $1,2,3,\\ldots $, and infinitely many real numbers, such as $0$, $1$, $\\pi$, etc. But are these two infinities the same?
​
Well, suppose you have two sets of objects, e.g. people and horses, and you want to know if the number of objects in one set is the same as in the other. The simplest way is to find a way of corresponding the objects one-to-one. For instance, if you see a parade of people riding horses, you will know that there are as many people as there are horses, because there is such a one-to-one correspondence.
​
We say that an set with infinitely many things is _countable_, if we can find a one-to-one correspondence between the things in this set and the natural numbers.
​
E.g., the integers are countable: $1\\leftrightarrow 0$, $2\\leftrightarrow -1$, $3\\leftrightarrow 1$, $4\\leftrightarrow -2$, $5\\leftrightarrow 2$, etc. gives such a correspondence.
​
However, the set of real numbers is NOT countable! This was proven for the first time by Georg Cantor. Here is a proof using the so-called [diagonal argument](http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument).
​
### Score: 6 · By: Conifold · Answered: 2014-05-23
​
This is an answer to the following question marked as duplicate which redirects here: "_I've known for some time that infinitary numbers can be different in order, such as the integers (countable), and the real numbers (uncountable). I read that you can always find a higher order of infinity given any order of infinity. Since infinity is the limit of the natural numbers under the successor function, I would like to know if there is a similar concept for orders of infinity under taking power-sets, if there is a sort of "super-infinity", a limit to the orders of infinity._"
​
Yes, there is such a concept: the smallest strongly inaccessible cardinal. Roughly, it is the smallest uncountable infinity that can not be reached by taking either unions or power sets of infinities under it, see here [http://en.wikipedia.org/wiki/Limit\_cardinal](http://en.wikipedia.org/wiki/Limit_cardinal). Existence of such cardinals is widely believed to be independent of the standard axioms of set theory (ZFC), in other words it can neither be proved nor disproved from them. However, there are many works, where people postulate existence of strongly inaccessible cardinals and see what they can derive from it.
​
Of course, even with such a postulate you still don't get the "infinity of all infinities", such a concept is self-contradictory according to the Russel paradox, but the smallest strongly inaccessible cardinal is in a similar relation to the ones under it regarding power sets as the countable cardinal is regarding successors and unions.
​
### Score: 2 · By: Royi · Answered: 2010-07-20
​
Just simple intuitive explanation.
​
How many Natural (Integers) Numbers could you count? There are infinitely many, yet you can count them. It's called [Countable Set](http://en.wikipedia.org/wiki/Countable_set).
​
How many Real Numbers are there? Infinitely as well (Since at least every Natural Number is a Real Number).
Yet you won't be able to count them (Intuitively, Let's say you name a number the first, then find the second, I can, for sure, find a number in between, their average which is Real Number as well). It's called [Uncountable Set](http://en.wikipedia.org/wiki/Uncountable_set).
​
What you are after is how we define how big is a given set.
Then you should look for [Cardinality](http://en.wikipedia.org/wiki/Cardinality).