Вопрос: Как объяснить разную скорость выполнения вложенных циклов в разных языках?

Лучший ответ: Меня как-то не устроило то, как вы оценили производительность Python, поэтому я взялся чуть подправить ваш пример для демонстрации совершенно других результатов. Запуск моего примера кроме установки numpy (pip install numpy), потребует установку еще одной интересной библиотеки (pip install numba) с ее установкой могут быть связанны некоторые трудности на различных ОС (она зависит еще и от llvm), но, поверьте, оно того стоит, полученные цифры производительности должны вам понравиться.
Для демонстрации реальной скорости вычислений в моем примере миллион итераций это довольно мало, камень не успевает хорошо прогреться. Обратите внимание, я заменил миллион итераций на 100 миллионов, поэтому полученный результат надо разделить на 100 для сравнения с другими языками. Вот, собственно, сам код:from numba import jit
import numpy


@jit
def inner_func(a_list, b_list):
    sum = 0
    j = 0
    for y in range(0, 16):
        for x in range(0, 16):
            p = a_list[j] - b_list[j]
            sum += p * p
            j += 1
    return sum


@jit
def outer_func(a_list, b_list):
    sum = 0
    for g in range(0, 100000000):  # 100 000 000 == 10^8 !!!
        sum += inner_func(a_list, b_list)
    return sum


def main():
    maxint = numpy.iinfo(numpy.intc).max
    a_list = numpy.random.randint(maxint, size=256)
    b_list = numpy.random.randint(maxint, size=256)
    sum = outer_func(a_list, b_list)
    print(sum)


if __name__ == '__main__':
    main()
Если вам удалось это запустить и полученные цифры вас впечатлили, то я бы попросил подправить в вашем вопросе ту часть, которая касается Python, для восстановления справедливости в отношении этого великолепного языка.

Худший ответ: Вообще в таких случаях все сводится к интерпретации (ну или исполнению машинного кода, если он машинный; по сути-то это та же интерпретация).
А именно, к двум факторам:
1) насколько хорошо оптимизирован алгоритм интерпретатора (алгоритм разбора кода, + не слишком ли много интерпретатор делает лишних операций, не связанных с выполнением кода, например, он может подгружать что-то там)
> Замерял время выполнения с помощью линуксовой команды time.
Это то есть вы смотрели не время выполнения алгоритма, а время выполнения программы в целом, от запуска до завершения? Ну там вообще куча причин может быть, интерпретатор не моментально запускается, и что он подгружает и делает при запуске, вообще одним авторам известно.
2) насколько минимизирован (и вообще оптимизирован для интерпретации) сам интерпретируемый код. Именно поэтому код в бинарном формате (машинный код, байт-код) потенциально быстрее, чем код в текстовом формате. Во-первых, бинарник тупо компактнее, скажем вместо слова function (которое занимает самый минимум 8 байт) может быть всего лишь 1-2 кракозябра. Во-вторых, бинарный формат - он строгий, всё там более однозначно и не бывает всей этой мути с пробелами, табами и пр., интерпретатору меньше приходится думать что же значит каждый байт вместе с байтами перед ним и байтами после него. Минимизация кода с помощью утилит помогает сделать его компактнее, но интерпретатор-то все равно проверяет на табы, пробелы и т.д., так что и минифицированный код в текстовом формате - все равно не очень быстр всегда.
Но в случае с Си, стандартные компиляторы по дефолту просто загаживают код всякой "дрянью", это отлично видно, если взять OllyDbg и сравнить хотя бы по длине с тем кодом, который дают компиляторы ассемблера.