import numpy as np
import math
g = 9.81
N = 1000
tau = 20.0
dt = tau/float(N-1)

SHO

state[0] : 늘어난거리, 위치
state[1] : 속도

dv_dt 유도식

      F = -mg -kx (탄성력)
      F = ma      (뉴턴 제2법칙 가속도법칙)
      ma = -mg -kx
      a = -g -(kx/m)

x(늘어난 거리)를 이용해서 가속도를 구해주는 것

euler 함수에 들어갈 [속도, 가속도]를 구해준다

def SHO(state, time):
    dx_dt = state[1]
    dv_dt = -k/m * state[0] - g
    return np.array([dx_dt, dv_dt])

euler

1차 일반 미분 방정식의 해를 근사시켜준다…
결국 Yn+1을 Yn을 이용해서 구해준다는 이야기

[Xn + v dt, Vn + a dt] == [Xn+1, Vn+1]

def euler(y, t, dt, f):
    return y + f(y, t) * dt

k : 탄성계수

m : 질량

x0 : 초기위치

v0 : 초기속도

k = 3.5
m = 0.2
x0 = 0
v0 = 0

t = np.linspace(0.0, tau, N)
y = np.zeros((N, 2))

y[0, 0] = x0
y[0, 1] = v0
for i in range(N-1):
    y[i+1] = euler(y[i], t[i], dt, SHO)
xdata = [y[i, 0] for i in range(N)]
vdata = [y[i, 1] for i in range(N)]
from pylab import *

add plot position

subplot(2,1,1)
plot(t, xdata)
xlabel("time")
ylabel("position")
<matplotlib.text.Text at 0x22a3a2c0780>

add plot velocity

subplot(2,1,2)
plot(t, vdata)
xlabel("time")
ylabel("velocity")
show()




저작자 표시 비영리 변경 금지
신고

WRITTEN BY
Jen6
jen6의 개발, 보안 블로그 까끔가다 쓸대 있는걸 올리려고 노력중

받은 트랙백이 없고 , 댓글이 없습니다.
secret
from random import random, seed
from math import sqrt

Monte Carlo Method

난수를 이용해 함수의 값을 확률적으로 계산하는 알고리즘
참고 url
몬테카를로 법을 이용해 pi의 근사값을 구해보자

  1. 반지름이 1인 원이 있다고 생각하자 ( $x^2 + y^2 = 1$ )
  2. 이제 그 원안에 점들을 찍는다.
    • 이때 난수가 사용된다. (점의 좌표 범위 : $ 0 \leq x \leq 1 , 0 \leq y \leq 1 $ )
    • random 함수의 값은 float으로 0~1 사이의 값이 리턴된다.
  3. 원의 넓이는 $\pi r^2$이고 정사각형의 넓이는 $4r^2$이다.
    따라서 원의 넓이를 정사각형의 넓이로 나누게 되면 $\frac{\pi}{4}$가 된다.

  4. 3번에서 구한 값에 4배를 해주면 원주율의 근사값이 나온다

#n은 점을 몇개 찍을것 인지를 지정해주는 변수 (n이 클수록 정확한 근사값을 얻을 수 있다.)
n = 10000
#inside, outside는 각각 원안에 원밖에 찍힌 점들을 저장해두는 list이다.
inside = []
outside = []
#n번 반복하면서 x, y에 random함수에서 나온 난수를 대입하고
#원안에 있는지 밖에 있는지 체크해서 넣어준다
for i in range(n):
    x = random()
    y = random()
    if sqrt(x*x + y*y) <= 1:
        inside.append([x, y])
    else:
        outside.append([x, y])
#원안에 찍힌 점들의 갯수 / 총 점의 갯수
pi = 4 * len(inside) / n
print('pi ≈ ', pi)
pi ≈  3.1436
#여기서부터는 찍힌 점을 그래프로 보여주는 코드이다. (읽을 필요 x)
import plotly.plotly as py
import plotly.graph_objs as go
inx, iny = zip(*inside)
outx, outy = zip(*outside)
inner_plot = go.Scatter (
    x = inx,
    y = iny,
    mode = 'markers',
    name = 'inCircle'
)

outter_plot = go.Scatter(
    x = outx,
    y = outy,
    mode = 'markers',
    name = 'outCircle'
)

data = [inner_plot, outter_plot]

layout = {
    'xaxis' : {
        'range' : [0, 1],
        'zeroline' : False,
        },
    'yaxis' : {
        'range' : [0, 1]
        },
    'shapes' : [
        {
            'type' : 'circle',
            'xref' : 'x',
            'yref' : 'y',
            'x0' : -1,
            'y0' : -1,
            'x1' : 1,
            'y1' : 1,
            'line' : {
                'color': 'rgba(0, 0, 0, 1)',
                'width' : 3,
            },
        },
    ]
}



fig = {
    'data' : data,
    'layout' : layout,
}
py.iplot(fig, filename='MonteCarlo_PI')
저작자 표시 비영리 변경 금지
신고

WRITTEN BY
Jen6
jen6의 개발, 보안 블로그 까끔가다 쓸대 있는걸 올리려고 노력중

받은 트랙백이 없고 , 댓글이 없습니다.
secret

CPPCon 2016 The strange details of std::string at Facebook

동영상 링크
ppt링크

뭐가 제일 페이스북에 효율적인지

string은 제일 중요한 요소중 하나
cpu전체의 18%가 std안에서 쓰임

string을 간단하게 만드는 것

gcc string(v < 5) Implementation

sizeof string is 8 (in gcc same as pointer)
다른 모든것보다 제일 많이 쓰이는 string? => empty string
but empty string is no empty
malloc을 해서 매 번 overhead를 감수하고 할껀가?
gcc는 매번 25byte arry를 가지고 있음 So empty is not empty

Q:왜 empty가 없는건데?
A:그러면 매 번 비어있는 string인지 체크해야함 if NullString || ptr != null_ptr 등등

gcc copy on write
copy 생성자를 받을때 original string의 레퍼런스를 하나 증가시킴 그후 메모리를 수정시킬때만 write함
(지금은 c++11 concurrency문제 때문에 drop)


fbstring

string관련 처리 코드에서 병목현상이 발생

  • 다른 페이지를 매번 접근
  • malloc에서 걸림

매번 힙을 사용하다 보니 문제가 생겨서 작은 사이즈의 string의 경우 스택을 사용해서 최적화를 진행

fbstring 구조

Normal String : data | size(14) | capacity(15) (data제외 29 바이트)

union

Small String : data \0 .... emty size (25바이트)

union으로 되어있기 때문에 small string의 사이즈를 넘어가게 되면 normal string으로 넘어가게 됨
이런 방식으로 하면 마지막에 널바이트로 덮으면서 남은 capacity도 표현 가능… 개똑똑)


최적화

  • normal string인지 small string인지 구분할 flag가 필요.
    facebook 에서는 JEmalloc이라는 메모리 할당을 씀
    bucket에서 쓸 수 있는 메모리를 리턴해주는데
    8byte align을 해서 29byte를 요청하면 32byte를 리턴해 줌.
    fbstring은 이 사실을 알고 있기 때문에 남은 3바이트를 flag에 사용하는 비트로 이용함
  • 일정 사이즈 이상 커지면 big size string으로 해서 ref conut를 사용(Copy on Write)

Performance of fbstring

gcc_string.size()

movq (%rdi), %rax
movq -24(%rax), %rax

fbstring.size()

movabsq $-4611686018427387904, %rax
testq %rax, 16(%rdi)
je .L7
----is_small-----
movq 8(%rdi), %rax
ret
.L7:
movsbq 23(%rdi), %rdx
movl $23, %eax
subq %rdx, %rax
ret

딱봐도 fbstring이 훨씬 길다.
small string인지 normal string인지 구분을 먼저하고 길이를 리턴 해야 하기 때 문에 라인 수도 더 길다.

근데 밴치마크를 하게 될 경우
gcc string : 1.6ns
fb string : 0.9 ns
???? 브랜치 까지 있는 9줄의 코드가 어떻게 하면 2줄짜리 코드보다 더 빠를 수 있지????

-> gcc string은 모두 힙을 쓰기 때문에 page fault가 자주 일어나게 됨 align된 string사이즈라면 fault가 더 적게 나서 fbstring보다 빠르지만 일반적인 경우 fbstring이 더 빠름

그래서 std::string 을 folly::fbstring으로 교체 해봤다.
-> 1% 성능향상 (적은것 같아 보일 수 있지만 fb에서 사용하는 모든 c++의 성능이 1%향상 되었다고 보면.. 티끌모아 태산이다. )

Killing the null terminator

fbstring lazily wrote \0

보통 string을 쓰나보면 push_back을 이용해서 concat하는 경우가 많음.
그래서 굳이 계속 \0을 붙여줄 필요 없이 필요할 때만 붙여줌
But this is illegal (표준에 맞는 구현이 아님 Concurrency를 생각하면 좋은 구현 X)
하지만 대부분의 사람은 null에 굳이 상관 없는 코드를 작성 하기 때문에 그냥 씀
c_str(), data()는 \0을 붙이게 됨

Problem in c_str()

const Char * c_str() const {
...
data[size()] = ‘\0’;
return data;
}

fb에서는 global read only string 변수를 두고 다양한 쓰레드에서 c_str()을 호출한다.
c_str은 구현대로 라면 const함수이기 때문에 원본 데이터에 대해서 변경이 없어야 함.
프로그래머 입장에서 보면 const라 데이터에 변화가 없다고 생각하지만 Cpu입장에서 보면 string마지막에 \0를 붙임으로써 cache line을 다 날려버린다..! 느려질 수 밖에

그래서 \0이 있는경우는 체크해서 data에 안쓰기로 결정!

const Char * c_str() const {
...
if (data[size()] != ‘\0’) //Problem Undefined behavior  
data[size()] = ‘\0’;
return data;
}

위에 저 if 안의 diff는 broken code.
초기화 되지 않은 메모리를 읽을 수 도 있음.
문자열 길이가 128바이트라면 129byte의 메모리가 필요함.
근데 je malloc에서 malloc을 하게 될 경우 128이란 숫자는 페이지 크기에 align 시키기 편한 숫자(gcd 4096 92) 이라 페이지의 맨 마지막(page last - 128)에 배치.

다른 97같이 align안 맞는 경우는 ok(뒤에 align을 맞추기 위해 보통 몇바이트 더 할당되기때문에)
128byte를 할당하면 페이지 맨 끝 부분에 할당되게 되면서 남는 메모리 공간이 없게됨

문제가 되는 부분은 if문

if(data[size()]==0)

data[size()]에 read 하게되면 129번째인데 할당되지도 않고 쓰지도 않은 메모리에 접근하게됨

근데 커널에서 Undefined mem(할당되지 않고 write도 안한 경우)에 접근하게되면 0을 리턴함. 그렇기 때문에 저 if문이 broken이라는 표현을 쓴듯
그래서 Null을 안쓰고 포인터를 리턴하게되고 write를 하게되면 믈리 페이지가 맵핑되면서 129번째에 널이 없는채로 리턴. 문자열 관련처리를 하다가 널을 찾아 3만리 떠날 수 있는 큰 문제

저작자 표시 비영리 변경 금지
신고

WRITTEN BY
Jen6
jen6의 개발, 보안 블로그 까끔가다 쓸대 있는걸 올리려고 노력중

받은 트랙백이 없고 , 댓글  3개가 달렸습니다.
  1. 이해가 쏙쏙되어요! 감사합니당 천사 건씌
  2. 정말 감사합니다 ! ^^ 오늘 행복한 하루 지내세요 ㅎㅎ
  3. 코잘남이되고싶어요 2017.04.05 17:53 신고
    역시 갓건! 정말 감사해요~
secret