SORU
26 Mayıs 2014, PAZARTESİ


Neden küçük bir liste daha küçük bir dize üzerinde yineleme için yavaş mı?

Etrafında timeit ile oynuyordum ve küçük bir dize üzerinde basit bir liste kavrama yapıyor küçük tek karakter dizeleri bir liste üzerinde aynı işlemi yapmak daha uzun sürdüğünü fark ettim. Herhangi bir açıklama var mı? Neredeyse 1.35 kat daha fazla zaman.

>>> from timeit import timeit
>>> timeit("[x for x in 'abc']")
2.0691067844831528
>>> timeit("[x for x in ['a', 'b', 'c']]")
1.5286479570345861

Bu neden daha düşük bir seviyede ne oluyor?

CEVAP
26 Mayıs 2014, PAZARTESİ


TL;DR

  • Gerçek hız farkı yükü çok fazla, Python 2 için çıkarılmış bir kez 70% (veya daha fazla) daha yakın.

  • Nesne oluşturmadeğilhatalı. Her iki yöntem tek karakter dizeleri önbelleğe yeni bir nesne oluşturur.

  • Fark unobvious, ama büyük olasılıkla dize dizin üzerinde kontrolleri daha fazla sayıda oluşturulur, türü ve sağlam getirmedi. Ayrıca geri dönüş için ne kontrol etmek için pek çok teşekkürler.

  • Dizin listesi oldukça hızlı.



>>> python3 -m timeit '[x for x in "abc"]'
1000000 loops, best of 3: 0.388 usec per loop

>>> python3 -m timeit '[x for x in ["a", "b", "c"]]'
1000000 loops, best of 3: 0.436 usec per loop

Bu buldum ne katılmıyoruz.

2, sonra Python kullanıyor olmalısınız.

>>> python2 -m timeit '[x for x in "abc"]'
1000000 loops, best of 3: 0.309 usec per loop

>>> python2 -m timeit '[x for x in ["a", "b", "c"]]'
1000000 loops, best of 3: 0.212 usec per loop

Hadi sürümleri arasındaki farkı açıklar. Derlenmiş kodu inceleyeceğim.

3: İçin Python

import dis

def list_iterate():
    [item for item in ["a", "b", "c"]]

dis.dis(list_iterate)
#>>>   4           0 LOAD_CONST               1 (<code object <listcomp> at 0x7f4d06b118a0, file "", line 4>)
#>>>               3 LOAD_CONST               2 ('list_iterate.<locals>.<listcomp>')
#>>>               6 MAKE_FUNCTION            0
#>>>               9 LOAD_CONST               3 ('a')
#>>>              12 LOAD_CONST               4 ('b')
#>>>              15 LOAD_CONST               5 ('c')
#>>>              18 BUILD_LIST               3
#>>>              21 GET_ITER
#>>>              22 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
#>>>              25 POP_TOP
#>>>              26 LOAD_CONST               0 (None)
#>>>              29 RETURN_VALUE

def string_iterate():
    [item for item in "abc"]

dis.dis(string_iterate)
#>>>  21           0 LOAD_CONST               1 (<code object <listcomp> at 0x7f4d06b17150, file "", line 21>)
#>>>               3 LOAD_CONST               2 ('string_iterate.<locals>.<listcomp>')
#>>>               6 MAKE_FUNCTION            0
#>>>               9 LOAD_CONST               3 ('abc')
#>>>              12 GET_ITER
#>>>              13 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
#>>>              16 POP_TOP
#>>>              17 LOAD_CONST               0 (None)
#>>>              20 RETURN_VALUE

Bu liste değişken listesinin bina nedeniyle yavaş her zaman olması muhtemel olduğunu burada görüyorsunuz.

Bu

 9 LOAD_CONST   3 ('a')
12 LOAD_CONST   4 ('b')
15 LOAD_CONST   5 ('c')
18 BUILD_LIST   3

bölüm. String değişken sadece

 9 LOAD_CONST   3 ('abc')

Bu bir fark yaratmak için görünüyor mu kontrol edebilirsiniz:

def string_iterate():
    [item for item in ("a", "b", "c")]

dis.dis(string_iterate)
#>>>  35           0 LOAD_CONST               1 (<code object <listcomp> at 0x7f4d068be660, file "", line 35>)
#>>>               3 LOAD_CONST               2 ('string_iterate.<locals>.<listcomp>')
#>>>               6 MAKE_FUNCTION            0
#>>>               9 LOAD_CONST               6 (('a', 'b', 'c'))
#>>>              12 GET_ITER
#>>>              13 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
#>>>              16 POP_TOP
#>>>              17 LOAD_CONST               0 (None)
#>>>              20 RETURN_VALUE

Bu sadece üretir

 9 LOAD_CONST               6 (('a', 'b', 'c'))

dizilerini değişmez. Test:

>>> python3 -m timeit '[x for x in ("a", "b", "c")]'
1000000 loops, best of 3: 0.369 usec per loop

Harika, hız geri.

2: İçin Python

def list_iterate():
    [item for item in ["a", "b", "c"]]

dis.dis(list_iterate)
#>>>   2           0 BUILD_LIST               0
#>>>               3 LOAD_CONST               1 ('a')
#>>>               6 LOAD_CONST               2 ('b')
#>>>               9 LOAD_CONST               3 ('c')
#>>>              12 BUILD_LIST               3
#>>>              15 GET_ITER            
#>>>         >>   16 FOR_ITER                12 (to 31)
#>>>              19 STORE_FAST               0 (item)
#>>>              22 LOAD_FAST                0 (item)
#>>>              25 LIST_APPEND              2
#>>>              28 JUMP_ABSOLUTE           16
#>>>         >>   31 POP_TOP             
#>>>              32 LOAD_CONST               0 (None)
#>>>              35 RETURN_VALUE        

def string_iterate():
    [item for item in "abc"]

dis.dis(string_iterate)
#>>>   2           0 BUILD_LIST               0
#>>>               3 LOAD_CONST               1 ('abc')
#>>>               6 GET_ITER            
#>>>         >>    7 FOR_ITER                12 (to 22)
#>>>              10 STORE_FAST               0 (item)
#>>>              13 LOAD_FAST                0 (item)
#>>>              16 LIST_APPEND              2
#>>>              19 JUMP_ABSOLUTE            7
#>>>         >>   22 POP_TOP             
#>>>              23 LOAD_CONST               0 (None)
#>>>              26 RETURN_VALUE        

Garip bir şey varaynıliste bina, ama hala bunun için daha hızlı. Python 2 fast garip davranıyor.

Bu kapsam ve yeniden zaman da kaldıralım. _ = optimize dışarı izin vermemektir.

>>> python3 -m timeit '_ = ["a", "b", "c"]'
10000000 loops, best of 3: 0.0707 usec per loop

>>> python3 -m timeit '_ = "abc"'
100000000 loops, best of 3: 0.0171 usec per loop

Hazırlama sürümleri arasındaki fark (bu sayılar küçük olduğu için hesap kadar önemli değildir. Böylece Python 3 kapsam yavaş olduğunu rahatlıkla söyleyebiliriz. Bu Python 3 değişti kapsam olarak anlamlı aklım başımda ölçüm yapar.

Şimdi kıyaslama (sadece yineleme değil havai kaldırıyorum) geliştirmek. Bu önceden atama ile iterable binası kaldırır:

>>> python3 -m timeit -s 'iterable = "abc"'           '[x for x in iterable]'
1000000 loops, best of 3: 0.387 usec per loop

>>> python3 -m timeit -s 'iterable = ["a", "b", "c"]' '[x for x in iterable]'
1000000 loops, best of 3: 0.368 usec per loop
>>> python2 -m timeit -s 'iterable = "abc"'           '[x for x in iterable]'
1000000 loops, best of 3: 0.309 usec per loop

>>> python2 -m timeit -s 'iterable = ["a", "b", "c"]' '[x for x in iterable]'
10000000 loops, best of 3: 0.164 usec per loop

*Eğer 64* arama yük olup olmadığını kontrol edebiliriz:

>>> python3 -m timeit -s 'iterable = "abc"'           'iter(iterable)'
10000000 loops, best of 3: 0.099 usec per loop

>>> python3 -m timeit -s 'iterable = ["a", "b", "c"]' 'iter(iterable)'
10000000 loops, best of 3: 0.1 usec per loop
>>> python2 -m timeit -s 'iterable = "abc"'           'iter(iterable)'
10000000 loops, best of 3: 0.0913 usec per loop

>>> python2 -m timeit -s 'iterable = ["a", "b", "c"]' 'iter(iterable)'
10000000 loops, best of 3: 0.0854 usec per loop

Hayır. Hayır, değil. Fark çok küçük, özellikle Python 3 için.

O yüzden daha da istenmeyen bir yük kaldırmak... her şey daha yavaş yaparak! Amaç sadece zaman gizler yükü çok uzun bir yineleme.

>>> python3 -m timeit -s 'import random; iterable = "".join(chr(random.randint(0, 127)) for _ in range(100000))' '[x for x in iterable]'
100 loops, best of 3: 3.12 msec per loop

>>> python3 -m timeit -s 'import random; iterable =        [chr(random.randint(0, 127)) for _ in range(100000)]' '[x for x in iterable]'
100 loops, best of 3: 2.77 msec per loop
>>> python2 -m timeit -s 'import random; iterable = "".join(chr(random.randint(0, 127)) for _ in range(100000))' '[x for x in iterable]'
100 loops, best of 3: 2.32 msec per loop

>>> python2 -m timeit -s 'import random; iterable =        [chr(random.randint(0, 127)) for _ in range(100000)]' '[x for x in iterable]'
100 loops, best of 3: 2.09 msec per loop

Aslında bu durum değişmediçokbiraz yardımcı oldu ama.

Bu yüzden bu kavrama çıkarın. Sorunun bir parçası değil, yükü:

>>> python3 -m timeit -s 'import random; iterable = "".join(chr(random.randint(0, 127)) for _ in range(100000))' 'for x in iterable: pass'
1000 loops, best of 3: 1.71 msec per loop

>>> python3 -m timeit -s 'import random; iterable =        [chr(random.randint(0, 127)) for _ in range(100000)]' 'for x in iterable: pass'
1000 loops, best of 3: 1.36 msec per loop
>>> python2 -m timeit -s 'import random; iterable = "".join(chr(random.randint(0, 127)) for _ in range(100000))' 'for x in iterable: pass'
1000 loops, best of 3: 1.27 msec per loop

>>> python2 -m timeit -s 'import random; iterable =        [chr(random.randint(0, 127)) for _ in range(100000)]' 'for x in iterable: pass'
1000 loops, best of 3: 935 usec per loop

Böyle daha iyi oldu! Biraz daha hızlı hala deque yineleme kullanarak elde edebiliriz. Temelde aynı şey amadaha hızlı:

>>> python3 -m timeit -s 'import random; from collections import deque; iterable = "".join(chr(random.randint(0, 127)) for _ in range(100000))' 'deque(iterable, maxlen=0)'
1000 loops, best of 3: 777 usec per loop

>>> python3 -m timeit -s 'import random; from collections import deque; iterable =        [chr(random.randint(0, 127)) for _ in range(100000)]' 'deque(iterable, maxlen=0)'
1000 loops, best of 3: 405 usec per loop
>>> python2 -m timeit -s 'import random; from collections import deque; iterable = "".join(chr(random.randint(0, 127)) for _ in range(100000))' 'deque(iterable, maxlen=0)'
1000 loops, best of 3: 805 usec per loop

>>> python2 -m timeit -s 'import random; from collections import deque; iterable =        [chr(random.randint(0, 127)) for _ in range(100000)]' 'deque(iterable, maxlen=0)'
1000 loops, best of 3: 438 usec per loop

Beni en çok ne etkiliyor Unicode bytestrings ile rekabet olmasıdır. Bu açıkça hem de bytes unicode deneyerek kontrol edebiliriz:

  • bytes

    >>> python3 -m timeit -s 'import random; from collections import deque; iterable = b"".join(chr(random.randint(0, 127)).encode("ascii") for _ in range(100000))' 'deque(iterable, maxlen=0)'                                                                    :(
    1000 loops, best of 3: 571 usec per loop
    
    >>> python3 -m timeit -s 'import random; from collections import deque; iterable =         [chr(random.randint(0, 127)).encode("ascii") for _ in range(100000)]' 'deque(iterable, maxlen=0)'
    1000 loops, best of 3: 394 usec per loop
    
    >>> python2 -m timeit -s 'import random; from collections import deque; iterable = b"".join(chr(random.randint(0, 127))                 for _ in range(100000))' 'deque(iterable, maxlen=0)'
    1000 loops, best of 3: 757 usec per loop
    
    >>> python2 -m timeit -s 'import random; from collections import deque; iterable =         [chr(random.randint(0, 127))                 for _ in range(100000)]' 'deque(iterable, maxlen=0)'
    1000 loops, best of 3: 438 usec per loop
    

    Burada Python 3 aslında görüyorsunuzdaha hızlıdaha Python 2.

  • unicode

    >>> python3 -m timeit -s 'import random; from collections import deque; iterable = u"".join(   chr(random.randint(0, 127)) for _ in range(100000))' 'deque(iterable, maxlen=0)'
    1000 loops, best of 3: 800 usec per loop
    
    >>> python3 -m timeit -s 'import random; from collections import deque; iterable =         [   chr(random.randint(0, 127)) for _ in range(100000)]' 'deque(iterable, maxlen=0)'
    1000 loops, best of 3: 394 usec per loop
    
    >>> python2 -m timeit -s 'import random; from collections import deque; iterable = u"".join(unichr(random.randint(0, 127)) for _ in range(100000))' 'deque(iterable, maxlen=0)'
    1000 loops, best of 3: 1.07 msec per loop
    
    >>> python2 -m timeit -s 'import random; from collections import deque; iterable =         [unichr(random.randint(0, 127)) for _ in range(100000)]' 'deque(iterable, maxlen=0)'
    1000 loops, best of 3: 469 usec per loop
    

    Yine, Python 3 Bu beklenen bir durum, ancak daha hızlıdır, (str Python 3'te ilgi çok olmuştur).

Aslında, unicode-bytes bu fark, etkileyici, çok küçük.

Diyelim ki bu bir dava, hızlı ve kullanışlı olarak benim için görerek analiz:

>>> python3 -m timeit -s 'import random; from collections import deque; iterable = "".join(chr(random.randint(0, 127)) for _ in range(100000))' 'deque(iterable, maxlen=0)'
1000 loops, best of 3: 777 usec per loop

>>> python3 -m timeit -s 'import random; from collections import deque; iterable =        [chr(random.randint(0, 127)) for _ in range(100000)]' 'deque(iterable, maxlen=0)'
1000 loops, best of 3: 405 usec per loop

Aslında Tim eleyebiliriz Peter 10 kat upvoted cevabı!

>>> foo = iterable[123]
>>> iterable[36] is foo
True

Bu yeni nesneler değildir!

Ama bu kayda değer: dizin oluşturmamaliyeti. Fark büyük olasılıkla yineleme ve sadece dizini Kaldır yani indeksleme olacak:

>>> python3 -m timeit -s 'import random; iterable = "".join(chr(random.randint(0, 127)) for _ in range(100000))' 'iterable[123]'
10000000 loops, best of 3: 0.0397 usec per loop

>>> python3 -m timeit -s 'import random; iterable =        [chr(random.randint(0, 127)) for _ in range(100000)]' 'iterable[123]'
10000000 loops, best of 3: 0.0374 usec per loop

Fark küçük gibi görünüyor, amaen azındanmaliyeti yarım yük:

>>> python3 -m timeit -s 'import random; iterable =        [chr(random.randint(0, 127)) for _ in range(100000)]' 'iterable; 123'
100000000 loops, best of 3: 0.0173 usec per loop

hız farkı yüzünden karar vermek için yeterlidir. Sanırım.

Neden bu kadar hızlı bir liste dizin oluşturma?

Peki, daha sonra geleceğim, ama tahminimce için kontrol edinstaj yaptımdizeleri (veya eğer ayrı bir mekanizma varsa, önbelleğe alınan karakterler). Bu daha hızlı daha uygun olacaktır. Ama kaynak C... rahat değilim rağmen) kontrol edeceğim.


Burada kaynak:

static PyObject *
unicode_getitem(PyObject *self, Py_ssize_t index)
{
    void *data;
    enum PyUnicode_Kind kind;
    Py_UCS4 ch;
    PyObject *res;

    if (!PyUnicode_Check(self) || PyUnicode_READY(self) == -1) {
        PyErr_BadArgument();
        return NULL;
    }
    if (index < 0 || index >= PyUnicode_GET_LENGTH(self)) {
        PyErr_SetString(PyExc_IndexError, "string index out of range");
        return NULL;
    }
    kind = PyUnicode_KIND(self);
    data = PyUnicode_DATA(self);
    ch = PyUnicode_READ(kind, data, index);
    if (ch < 256)
        return get_latin1_char(ch);

    res = PyUnicode_New(1, ch);
    if (res == NULL)
        return NULL;
    kind = PyUnicode_KIND(res);
    data = PyUnicode_DATA(res);
    PyUnicode_WRITE(kind, data, 0, ch);
    assert(_PyUnicode_CheckConsistency(res, 1));
    return res;
}

Üstünden yürürken, bazı kontroller yapacağız. Bu sıkıcı. O zaman biraz da sıkıcı olmalı atar. İlk ilginç çizgidir

ch = PyUnicode_READ(kind, data, index);

ama ederdikumutbu dizin tarafından bitişik C diziden okuyoruz kadar hızlı. Sonuç, ch, get_latin1_char(ch) önbelleğe karakteri iade ederiz 256'dan daha az olacaktır.

Çalıştır (ilk kontrolleri bırakarak) yapacağız

kind = PyUnicode_KIND(self);
data = PyUnicode_DATA(self);
ch = PyUnicode_READ(kind, data, index);
return get_latin1_char(ch);

Nerede

#define PyUnicode_KIND(op) \
    (assert(PyUnicode_Check(op)), \
     assert(PyUnicode_IS_READY(op)),            \
     ((PyASCIIObject *)(op))->state.kind)

iddia debug hızlı olduklarını kontrol edebilmem [] ((PyASCIIObject *)(op))->state.kind) (sanırım) bir yönlendirme ve C-düzey bir dökme göz ardı çünkü sıkıcı olan);

#define PyUnicode_DATA(op) \
    (assert(PyUnicode_Check(op)), \
     PyUnicode_IS_COMPACT(op) ? _PyUnicode_COMPACT_DATA(op) :   \
     _PyUnicode_NONCOMPACT_DATA(op))

ayrıca benzer nedenlerle, makroları (Something_CAPITALIZED) hızlı varsayarak sıkıcı olan)

#define PyUnicode_READ(kind, data, index) \
    ((Py_UCS4) \
    ((kind) == PyUnicode_1BYTE_KIND ? \
        ((const Py_UCS1 *)(data))[(index)] : \
        ((kind) == PyUnicode_2BYTE_KIND ? \
            ((const Py_UCS2 *)(data))[(index)] : \
            ((const Py_UCS4 *)(data))[(index)] \
        ) \
    ))

dizinler içerir ama gerçekten hiç yavaş değil ()

static PyObject*
get_latin1_char(unsigned char ch)
{
    PyObject *unicode = unicode_latin1[ch];
    if (!unicode) {
        unicode = PyUnicode_New(1, ch);
        if (!unicode)
            return NULL;
        PyUnicode_1BYTE_DATA(unicode)[0] = ch;
        assert(_PyUnicode_CheckConsistency(unicode, 1));
        unicode_latin1[ch] = unicode;
    }
    Py_INCREF(unicode);
    return unicode;
}

Şüphelerimi doğrulayan:

  • Bu önbelleğe alınan:

    PyObject *unicode = unicode_latin1[ch];
    
  • Bu hızlı olmalıdır. if (!unicode) çalışma değildir, bu durumda, tam anlamıyla denk geliyor

    PyObject *unicode = unicode_latin1[ch];
    Py_INCREF(unicode);
    return unicode;
    

Dürüst olmak gerekirse, asserttest ettikten sonra hızlı s (onları [İ . devre dışı bırakarak ^em>düşünüyorumiddia üzerine C-düzey çalışır...]), makulü yavaş tek parça

PyUnicode_IS_COMPACT(op)
_PyUnicode_COMPACT_DATA(op)
_PyUnicode_NONCOMPACT_DATA(op)

Olan:

#define PyUnicode_IS_COMPACT(op) \
    (((PyASCIIObject*)(op))->state.compact)

(hızlı, daha önce olduğu gibi),

#define _PyUnicode_COMPACT_DATA(op)                     \
    (PyUnicode_IS_ASCII(op) ?                   \
     ((void*)((PyASCIIObject*)(op)   1)) :              \
     ((void*)((PyCompactUnicodeObject*)(op)   1)))

hızlı eğer 107 ** makro, hızlı, ve

#define _PyUnicode_NONCOMPACT_DATA(op)                  \
    (assert(((PyUnicodeObject*)(op))->data.any),        \
     ((((PyUnicodeObject *)(op))->data.any)))

(iddia yönlendirme artı bir artı bir döküm bir o kadar da hızlı).

İndik (tavşan deliği):

PyUnicode_IS_ASCII

#define PyUnicode_IS_ASCII(op)                   \
    (assert(PyUnicode_Check(op)),                \
     assert(PyUnicode_IS_READY(op)),             \
     ((PyASCIIObject*)op)->state.ascii)

Hmm... öyle görünüyor ki... çok hızlı


Peki, o zaman hadi 111 ** karşılaştır. (EvetteşekkürlerBeni daha fazla iş verilmesi için Tim Peters :P)

PyObject *
PyList_GetItem(PyObject *op, Py_ssize_t i)
{
    if (!PyList_Check(op)) {
        PyErr_BadInternalCall();
        return NULL;
    }
    if (i < 0 || i >= Py_SIZE(op)) {
        if (indexerr == NULL) {
            indexerr = PyUnicode_FromString(
                "list index out of range");
            if (indexerr == NULL)
                return NULL;
        }
        PyErr_SetObject(PyExc_IndexError, indexerr);
        return NULL;
    }
    return ((PyListObject *)op) -> ob_item[i];
}

-Hata olmayan durumlarda bu sadece çalıştırmak için:

PyList_Check(op)
Py_SIZE(op)
((PyListObject *)op) -> ob_item[i]

PyList_Check nerede olduğunu

#define PyList_Check(op) \
     PyType_FastSubclass(Py_TYPE(op), Py_TPFLAGS_LIST_SUBCLASS)

(TABS! TABS!!!) (issue21587)Sabit ve birleştirilmiş5 dakika. Gibi... evet. Lanet olsun. Utanç Skeet koydular.

#define Py_SIZE(ob)             (((PyVarObject*)(ob))->ob_size)
#define PyType_FastSubclass(t,f)  PyType_HasFeature(t,f)
#ifdef Py_LIMITED_API
#define PyType_HasFeature(t,f)  ((PyType_GetFlags(t) & (f)) != 0)
#else
#define PyType_HasFeature(t,f)  (((t)->tp_flags & (f)) != 0)
#endif

Bu Py_LIMITED_API olmadığı sürece normalde çok önemsiz (iki indirections ve boolean birkaç Çek), bu durumda... ???

Sonra dizin oluşturma ve dökme (((PyListObject *)op) -> ob_item[i]) var ve işimiz bitti.

Kesinlikle vardırdaha azlisteler ve küçük hız farkları denetler kesinlikle ilgili olması olasıdır.


Genel olarak, sadece daha fazla tür denetleme ve yönlendirme (->) unicode için var sanırım. Bir noktayı kaçırıyorum gibi görünüyor, amane?

Bunu Paylaş:
  • Google+
  • E-Posta
Etiketler:

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • JayzTwoCents

    JayzTwoCents

    26 AĞUSTOS 2012
  • MandMEvangelists

    MandMEvangel

    28 Ocak 2008
  • undrmyumbrellaa

    undrmyumbrel

    25 Temmuz 2012