LINUX.ORG.RU

ФВП и производительность

 , , ,


2

7

Провёл тест на скорость работы одной и той же функции, написанной нормально и через ФВП. Получил потерю производительности в полтора раза:

SBCL:

(declaim (optimize (speed 3) (safety 0)))

(asdf:oos 'asdf:load-op :alexandria)

(defun f (x)
  (+ (+ (+ x 1) 2) 1))

(let ((f-comp
          (alexandria:compose
            (lambda (x) (+ x 1))
            (lambda (x) (+ x 2))
            (lambda (x) (+ x 1)))))
  (defun f-comp (x)
     (funcall f-comp x)))

(defconstant iter 10000000)

(time
 (dotimes (i iter)
   (f i)))

(time
 (dotimes (i iter)
   (f-comp i)))


Evaluation took:
  0.181 seconds of real time
  0.180000 seconds of total run time (0.180000 user, 0.000000 system)
  99.45% CPU
  325,363,554 processor cycles
  0 bytes consed

Evaluation took:
  0.296 seconds of real time
  0.296000 seconds of total run time (0.296000 user, 0.000000 system)
  100.00% CPU
  530,610,480 processor cycles
  0 bytes consed

Racket:

#lang racket
(define (f x)
  (+ (+ (+ x 1) 2) 1))

(define f-comp
  (compose
   (lambda (x) (+ x 1))
   (lambda (x) (+ x 2))
   (lambda (x) (+ x 1))))

(define iter 1000000)

(time 
 (for ([i iter])
   (f i)))

(time 
 (for ([i iter])
   (f-comp i)))

cpu time: 728 real time: 726 gc time: 0
cpu time: 1244 real time: 1244 gc time: 0

Получается, функции высшего порядка лучше не использовать? А как с этим борются в Haskell, если там без них почти ничего написать нельзя (точнее не принято рекомендуемым стилем программирования)?

★★★★★

Не угадал автора по заголовку.

Deleted ()

Racket

Толсто.

По теме — классическая дилемма, что важнее — время программиста или время выполнения. Ответ — когда как.

Debasher ★★★★★ ()
Последнее исправление: Debasher (всего исправлений: 1)
Ответ на: комментарий от Debasher

Толсто

Я перебрал те функциональные языки, что были под рукой (SBCL, Racket). Не на Си++ же проверять.

На Haskell не проверял, так как не умею там функцию многократно выполнить (ленивость, чистота и всё такое).

monk ★★★★★ ()

Непонятно, что такое твой этот compose и почему в варианте на рэкете ты его вызываешь каждый раз в функции.

Deleted ()
Ответ на: комментарий от Debasher

время программиста или время выполнения. Ответ — когда как.

ФВП не уменьшает время программиста. Только делает более красивый/удобный интерфейс.

Более того, если брать лиспы, то всё сводится к тому, что compose должен быть не функцией, а макросом, преобразующим

(alexandria:compose
            (lambda (x) (+ x 1))
            (lambda (x) (+ x 2))
            (lambda (x) (+ x 1)))
в
(lambda (x) (+ (+ (+ x 1) 2 1))))

Технически вполне реализуемо...

monk ★★★★★ ()

В GHC можно настрогать rewrite rules/SPECIALIZE для особых случаев.

good_riddance ()
Ответ на: комментарий от Deleted

что такое твой этот compose

По смыслу

(define (compose f . fs)  
  (cond 
    [(null? fs) f]
    [else 
     (define rest-f (apply compose fs))
     (lambda (x) (f (rest-f x)))]))

почему в варианте на рэкете ты его вызываешь каждый раз в функции

Не каждый раз. Он вызывается один раз и возвращает f-comp

monk ★★★★★ ()

The First Rule of Program Optimization: Don't do it.

The Second Rule of Program Optimization – For experts only: Don't do it yet.

ados ★★★★★ ()
Последнее исправление: ados (всего исправлений: 1)
Ответ на: комментарий от good_riddance

rewrite rules/SPECIALIZE для особых случаев

Ух ты!!! DEFINE-COMPILER-MACRO в Haskell! Спасибо, не знал.

monk ★★★★★ ()

Ожидаемо же что косвенный вызов хуже прямого. Другое дело, что оптимизатор мог бы такие лямбды инлайнить, афаик в C++ такое делается.

anonymous ()
Ответ на: комментарий от ados

The First Rule of Program Optimization: Don't do it

Так родилась Java. А потом всё-таки пришлось почти всё оптимизировать.

monk ★★★★★ ()
Ответ на: комментарий от monk

Вот эта жаба сейчас повсюду, когда как твой лисп никому не нужен.

ados ★★★★★ ()
Последнее исправление: ados (всего исправлений: 1)
Ответ на: комментарий от monk

ФВП не уменьшает время программиста. Только делает более красивый/удобный интерфейс.

Было бы point-free вместо всяких

(lambda (x) (+ x 1))

тогда можно было бы поговорить о красивом/удобном интерфейсе. В clojure же есть ->.

x3al ★★★★★ ()
Ответ на: комментарий от x3al

Было бы point-free вместо всяких

Можно и

(define f-comp
  (compose
   (curry + 1)
   (curry + 2)
   (curry + 1)))

Только тогда скорость становится уже в 10 раз, а не 1.5:

cpu time: 728 real time: 730 gc time: 0
cpu time: 6056 real time: 6046 gc time: 132

monk ★★★★★ ()
Последнее исправление: monk (всего исправлений: 1)
Ответ на: комментарий от monk

лiл

import timeit

hof_start = '''
def cmps(*args):
	def inner(x):
		for f in args[::-1]:
			x = f(x)
		return x
	return inner

f = cmps(lambda x: x+1, lambda x: x+2, lambda x: x+1)
'''

simple_start = '''
def f(x):
	return x + 1 + 2 + 1
'''

print timeit.timeit('f(10000)', setup=hof_start)
print timeit.timeit('f(10000)', setup=simple_start)

$ python hof.py 
2.32397389412
0.566710948944

Ну было бы глупо ожидать, что выдроченная сишная арифметика будет на одном уровне с пердолингом в пистонообъекты.

Deleted ()

Получается, функции высшего порядка лучше не использовать?

Весь ФП лучше не использовать, если нужна производительность

Почему? ФП это сахар над обычной императивщиной которая в разы эффективнее гоняется на цпу.

umren ★★★★★ ()
Ответ на: комментарий от umren

Весь ФП лучше не использовать

А в Haskell?

P.S. протестировал на C++14 в G++. Скорость для ФВП и напрямую одинакова.

monk ★★★★★ ()

Вот мне интересно - ну выиграл вот так ты 0.1 сек, повыкидывав 1000000*4 вызовов ФПВ. Что ты там делаешь, если тебе нужна такая оптимизация?

ados ★★★★★ ()
Последнее исправление: ados (всего исправлений: 1)
Ответ на: комментарий от monk

Как насчет тестов не на арифметике, а на чем-нибудь адекватном? Сразу будет видно, что стоимостью композиции можно пренебречь?

Deleted ()
Ответ на: лiл от Deleted

Теперь это бессмысленных микробенчмарков тред

public static void main(String[] argv) {
        Function<Integer, Integer> f1 = (i) -> i+1;
        Function<Integer, Integer> f2 = (i) -> i+2;
        Function<Integer, Integer> f3 = (i) -> i+1;
        int iter = 10000000;
        // simple
        long startTime1 = System.currentTimeMillis();
        for(int i = 0; i < iter; i++) {
            f(i);
        }
        long endTime1 = System.currentTimeMillis();
        // hof
        long startTime2 = System.currentTimeMillis();
        for(int i = 0; i < iter; i++) {
            f1.compose(f2).compose(f3).apply(i);
        }
        long endTime2 = System.currentTimeMillis();
        System.out.format("Time elapsed simple: %d ms%n", endTime1 - startTime1);
        System.out.format("Time elapsed hof: %d ms%n", endTime2 - startTime2);
    }

    static int f(int x) {
        return x + 1 + 2 + 1;
    }
Time elapsed simple: 4 ms
Time elapsed hof: 183 ms
Midael ★★★★★ ()
Последнее исправление: Midael (всего исправлений: 1)
Ответ на: комментарий от monk

А в Haskell?

идиоматичный хаскель не такой быстрый если сравнивать с C/C++

протестировал на C++14 в G++. Скорость для ФВП и напрямую одинакова.

Тут такое дело, там миллион оптимизаций.

ФП вцелом это всегда полагатся на дядь которые пишут компилятор, что бы они для всех твоих ФП кейсов сделали оптимизации которые в реальности выпримят твой код и сделают его опять же императивным перед исполнением.

Хорошо это или плохо - решать тебе.

umren ★★★★★ ()

Основные тормоза от compose, а не от ФВП. В Racket, насколько я видел, это уже оптимизировано давно.

#lang racket

(define (f x)
  (+ (+ (+ x 1) 2) 1))

(define f-comp
  (compose
   (lambda (x) (+ x 1))
   (lambda (x) (+ x 2))
   (lambda (x) (+ x 1))))

(define f-comp1
  (compose
   (lambda (x) (+ x 1))
   (lambda (x) (+ x 2))
   (lambda (x) (+ x 1))))

(define-syntax my-compose1
  (syntax-rules ()
    [(_)
     (lambda (x) x)]
    [(_ p0 p ...)
     (lambda (x)
       (p0 ((my-compose1 p ...) x)))]))  

(define my-comp1
  (my-compose1
   (lambda (x) (+ x 1))
   (lambda (x) (+ x 2))
   (lambda (x) (+ x 1))))

(define iter 10000000)

(define-syntax-rule (Test caption proc-id)
  (begin
    (displayln caption)
    (collect-garbage)
    (collect-garbage)
    (collect-garbage)
    (time 
     (for ([i (in-range iter)])
         (proc-id i)))))  

(Test "w/o compose" f)

(Test "using compose" f-comp)

(Test "using compose1" f-comp1)
 
(Test "using my-compose1" my-comp1)
w/o compose
cpu time: 78 real time: 89 gc time: 0
using compose
cpu time: 297 real time: 293 gc time: 0
using compose1
cpu time: 266 real time: 271 gc time: 0
using my-compose1
cpu time: 94 real time: 94 gc time: 0

qaqa ()
Ответ на: комментарий от qaqa

(define-syntax my-compose1

Это уже не ФВП. Это макрос. Я уже писал ФВП и производительность (комментарий)

С макросами проще, но их сложнее комбинировать. Например, (apply my-compose list-of-funs) уже не сделаешь

monk ★★★★★ ()
Последнее исправление: monk (всего исправлений: 1)
Ответ на: комментарий от monk

Только тогда скорость становится уже в 10 раз, а не 1.5:

(def iter 100000000)
(defn f-comp ([x] (-> x (+ 1) (+ 2) (+ 1))))
(defn f ([x] (+ (+ (+ x 1) 2) 1)))
(time (dotimes [i iter] (f i)))
(time (dotimes [i iter] (f-comp i)))
"Elapsed time: 2946.001212 msecs"
"Elapsed time: 2829.189484 msecs"

ЧЯДНТ? Время в 10 раз больше т.к. iter в 10 раз больше.

x3al ★★★★★ ()
Ответ на: комментарий от privet

Так они ж медленнее, чем синтаксис ->.

(def f-composed (apply comp (list #(+ % 1) #(+ % 2) #(+ % 1))))
(time (dotimes [i iter] (f-composed i)))
"Elapsed time: 5827.191356 msecs"
x3al ★★★★★ ()
Ответ на: комментарий от x3al

Можно и честно с partial сделать в point-free, но нафиг? Суть в том, что синтаксис compose нифига не удобен, если у тебя не каррированные функции и этот синтаксис можно получить с той же ->. Каррировать в clojure реально, но быстрее от этого не будет.

x3al ★★★★★ ()

Всё таки не думал, что ТС такой дурак

anonymous ()
Ответ на: комментарий от x3al

Ну дык про то и тред) ФВП тормозят, макросы, как уже сказано, не вставишь туда, куда мог бы вставить ФВП. Стройная картина в лиспах портится от этого разделения...

privet ()
Ответ на: комментарий от privet

Хз, я не настоящий лиспер, но в clojure мне хватает сахара -> в 99% случаев, а если реально нехватает — comp есть из коробки.

x3al ★★★★★ ()
Ответ на: комментарий от privet

Фигня это всё. Мне когда производительность нужна была, и всё дело было именно в цпу, то никакой разницы между циклами и map (точнее, map-into) я не заметил, да и компилятор превращает это дело в циклы. Вот с reduce было чуть хуже, но тоже терпимо. А писать всякие (compose f1 f2) в лиспе будет только дурачок как ТС, которому важна не программа, а какие-то его извращения. Просто в лиспе это дико неудобно

anonymous ()
Ответ на: комментарий от umren

Угу. Программы пишутся для работы на машине Неймана которой уже давно не существует. Железяки пытаются притворяться этой машиной, что бы программы быстро работали.

zinfandel ★★ ()
Ответ на: комментарий от umren

define императивный код

А главное, почему он быстрее выполняется?

zinfandel ★★ ()
Ответ на: комментарий от x3al

Ну вообще да, мне тоже использовать сам compose как фвп не приходилось.

privet ()
Ответ на: комментарий от anonymous

В очередной раз забаненный anonimous набежал и попытался самоутвердиться.

qaqa ()
Ответ на: комментарий от anonymous

Ну почему, иногда удобно. И симпатичней выглядит:

(map (compose f3 f2 f1)
     lst)

(map (λ (v) (f3 (f2 (f1 v))))
     lst)

privet ()
Ответ на: комментарий от privet

Это как буква-ламбда вместо слова lambda. Лучше просто избежать этого (f1 (f2 (f3 x))) на лиспе. Честно, никогда не приходилось этим пользоваться. Просто подумать, что в твоих функциях не так, что приходится пользоваться таким паровозом.

Есть языки, где специально проходят такие трюки типа «сконструируй новую функцию из уже имеющихся». Что лисп, что хаскель тут рядом не стояли. Лисп — обычная императивщина, ну пусть и с возможностью дать функцию как аргумент другой (хотя это даже в C есть). Поэтому не стоит увлекаться всяким compose и прочим. Если что я пишу (lambda ...) или даже пользуюсь flet для удобочитаемости.

anonymous ()
Ответ на: комментарий от anonymous

Лучше просто избежать этого (f1 (f2 (f3 x))) на лиспе. Честно, никогда не приходилось этим пользоваться. Просто подумать, что в твоих функциях не так, что приходится пользоваться таким паровозом.

А если функции изкоробочные?

;; Use of `->` (the "thread-first" macro) can help make code
;; more readable by removing nesting. It can be especially
;; useful when using host methods:

;; Arguably a bit cumbersome to read:
user=> (first (.split (.replace (.toUpperCase "a b c d") "A" "X") " "))
"X"

;; Perhaps easier to read:
user=> (-> "a b c d" 
           .toUpperCase 
           (.replace "A" "X") 
           (.split " ") 
           first)
"X"

☝ из мануала по кложуре. compose делает примерно то же, что и ->, но с обратным порядком функций, без автоподстановки аргумента и обычно манипулирует с каррированными функциями (иначе он нафиг не нужен). Ну и абстрактный compose в вакууме может быть функцией, а не макросом.

В очередной раз скажу: compose в языках без автокаррирования практически не нужен в чистом виде.

x3al ★★★★★ ()
Последнее исправление: x3al (всего исправлений: 1)
Ответ на: комментарий от x3al

Это опять же, кожура это поддерживает. А чтобы в CL сделать так же, но чтобы и универсально, и ТС не вопил «ай-ай, у меня тормозаа», надо попотеть. Так что лучше избежать этого.

В этом примере вообще нужна только часть строки до пробела. От этого надо и плясать)

anonymous ()

производительность

haskell, lisp

anonymous ()
Ответ на: комментарий от anonymous

А чтобы в CL сделать так же, но чтобы и универсально, и ТС не вопил «ай-ай, у меня тормозаа», надо попотеть. Так что лучше избежать этого.

Я даже больше скажу: у ТС с generic-версией compose оно распухнет больше исходного варианта. Потому, что как минимум там, где было (.replace "A" "X"), будет лямбда, чтобы показать, на каком месте функция .replace ждёт нужный аргумент. То же самое со .split. Избавляться от лямбд — только каррированием.

Почему в кложуре не нужны лямбды? Потому, что -> читерит и подставляет аргумент ровно там, где его ожидает 90% функций: на втором месте в форме вместо того, чтобы каррировать. Если аргумент нужен последним... есть ->>. Всё. Практично, быстро, чистый сахар. А в обычных лиспах это жутко неидиоматичный код.

Можно, конечно, эмулировать именно такое поведение, но это уже не чистый compose, а макро для вполне конкретных задач. В clojure оно называется thread through, по сути — pipe (перевёрнутый compose), в который заодно встроен аргумент. Вытащить аргумент обратно можно примерно таким clojure-сахаром: #(-> % fun1 fun2 fun3) если очень хочется (вроде того примера с map чуть выше), но на практике чаще оно нужно вместе с аргументом.

x3al ★★★★★ ()
Ответ на: комментарий от cdshines

Вы еще функции каждый раз заново генерируете. Если сделать compose один раз, все еще быстрее получается.

public class AppTest {
	@Test
	public void testCompose() throws Exception {
		long start = System.currentTimeMillis();
		for(Integer i = 0; i < 10000; i++){
			simple(i);
		}
		System.out.format("Simple Time: %s \n", System.currentTimeMillis() - start);

		start = System.currentTimeMillis();
		Function f = hof();
		for(Integer i = 0; i < 10000; i++) {
			f.apply(i);
		}
		System.out.format("HOF Time: %s \n", System.currentTimeMillis() - start);

		start = System.currentTimeMillis();
		IntUnaryOperator o = oHof();
		for(int i = 0; i < 10000; i++) {
			o.applyAsInt(i);
		}
		System.out.format("O HOF Time: %s \n", System.currentTimeMillis() - start);
	}

	private Integer simple(Integer i) {
		return i + 1 + 1 + 1;
	}

	private Function hof() {
		return ((Function<Integer, Integer>)(i) -> i + 1)
			.compose((Function<Integer, Integer>) (i) -> i + 1)
			.compose((Function<Integer, Integer>)(i) -> i + 1);
	}

	private IntUnaryOperator oHof() {
		return ((IntUnaryOperator) i -> i + 1)
			.compose(i -> i + 1)
			.compose(i -> i + 1);
	}
}
Simple Time: 7 
HOF Time: 95 
O HOF Time: 24 
DiKeert ★★ ()
Последнее исправление: DiKeert (всего исправлений: 2)
Ответ на: комментарий от anonymous

Просто подумать, что в твоих функциях не так, что приходится пользоваться таким паровозом

Я бы сказал наоборот, с ними как раз все так. Программа разделенная на маленькие функции которые потом вот так собираешь. И код-реюз в подарок.

Другое дело на практике редко красиво выходит. Одну функцию нужно закаррировать, другую тоже но там нужный аргумент в середине и хрен ее закаррируешь, а третья вообще макросом оказывается, и в итоге compose превращается в гавно и его лучше выкинуть.

В рэкете еще миксины определены как функции. Для больших иерархий без compose вообще не распарсишь кто там от кого наследуется.

privet ()

Теперь еще и жависты налетели со своим боксингом до кучи.

dave ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.