The second story

Tips for Improving Time-Critical Code

드레 — Fri, 25 Mar 2005 02:26:48 GMT

Sorting and Searching
Sorting is inherently time consuming compared to many typical operations. The best way to avoid unnecessary slowdown is to avoid sorting at critical times. You may be able to:

Defer sorting until a non-performance–critical time.
Sort the data at an earlier, non-performance–critical time.
Sort only the part of the data that truly needs sorting.
Sometimes, you can build the list in sorted order. Be careful, because if you need to insert data in sorted order, you may require a more complicated data structure with poor locality of reference, leading to cache misses and page faults. There is no approach that works in all cases. Try several approaches and measure the differences.

Here are some general tips for sorting:

Use a stock sort to minimize bugs.
Any work you can do beforehand to reduce the complexity of the sort is worthwhile. If a one-time pass over your data simplifies the comparisons and reduces the sort from O(n log n) to O(n), you will almost certainly come out ahead.
Think about the locality of reference of the sort algorithm and the data you expect it to run on.
There are fewer alternatives for searches than for sorting. If the search is time-critical, a binary search or hash table lookup is almost always best, but as with sorting, you must keep locality in mind. A linear search through a small array can be faster than a binary search through a data structure with a lot of pointers that causes page faults or cache misses.

Shared Libraries
Code reuse is desirable. However, if you are going to use someone else's code, you should make sure you know exactly what it does in those cases where performance is critical to you. The best way to understand this is by stepping through the source code or by measuring with tools such as PView or Performance Monitor.

Heaps
Use multiple heaps with discretion. Additional heaps created with HeapCreate and HeapAlloc let you manage and then dispose of a related set of allocations. Don't commit too much memory. If you're using multiple heaps, pay special attention to the amount of memory that is initially committed.

Instead of multiple heaps, you can use helper functions to interface between your code and the default heap. Helper functions facilitate custom allocation strategies that can improve the performance of your application. For example, if you frequently perform small allocations, you may want to localize these allocations to one part of the default heap. You can allocate a large block of memory and then use a helper function to suballocate from that block. If you do this, you will not have additional heaps with unused memory because the allocation is coming out of the default heap.

In some cases, however, using the default heap can reduce locality of reference. Use Process Viewer, Spy++, or Performance Monitor to measure the effects of moving objects from heap to heap.

Measure your heaps so you can account for every allocation on the heap. Use the C run-time debug heap routines to checkpoint and dump your heap. You can read the output into a spreadsheet program like Microsoft Excel and use pivot tables to view the results. Note the total number, size, and distribution of allocations. Compare these with the size of working sets. Also look at the clustering of related-sized objects.

You can also use the performance counters to monitor memory usage.

Threads
For background tasks, effective idle handling of events may be faster than using threads. It's easier to understand locality of reference in a single-threaded program.

A good rule of thumb is to use a thread only if an operating system notification that you block on is at the root of the background work. Threads are the best solution in such a case because it is impractical to block a main thread on an event.

Threads also present communication problems. You must manage the communication link between your threads, with a list of messages or by allocating and using shared memory. Managing the communication link usually requires synchronization to avoid race conditions and deadlock problems. This complexity can easily turn into bugs and performance problems.

For additional information, see Idle Loop Processing and Multithreading.

Small Working Set
Smaller working sets mean better locality of reference, fewer page faults, and more cache hits. The process working set is the closest metric the operating system directly provides for measuring locality of reference.

ㆍTo set the upper and lower limits of the working set, use SetProcessWorkingSetSize.
ㆍTo get the upper and lower limits of the working set, use GetProcessWorkingSetSize.
ㆍTo view the size of the working set, use Spy++.

ms-help://MS.MSDNQTR.2003FEB.1033/vccore/html/_core_tips_for_improving_time.2d.critical_code.htm

Dynamic Clustering..

드레 — Wed, 23 Mar 2005 09:32:34 GMT

그림은 분산 서버를 구현하는 방법을 나타낸다. 그 중에 나에 눈에 띄는 방식이 있어 올려본다. Dynamic Clustering..

아마 Sphere-Tree의 알고리즘을 이용하지 않을까 라는 생각이다.

JAVA LiveConnect

드레 — Wed, 23 Mar 2005 01:53:37 GMT

JavaScript to Java communication :
ㆍ http://wp.netscape.com/eng/mozilla/3.0/handbook/javascript/livecon.htm#1007749

LiveConnect provides three ways for JavaScript to communicate with Java:

Call Java methods directly.
Control Java applets.
Control Java plug-ins.
more...

Java to JavaScript communication
ㆍ http://wp.netscape.com/eng/mozilla/3.0/handbook/javascript/livecon.htm#1007828
To access JavaScript methods, properties, and data structures from your Java applet, import the Netscape javascript package:

import netscape.javascript.*
The package netscape.javascript defines the JSObject class and the JSException exception object.
The author of an HTML page must permit an applet to access JavaScript by specifying the MAYSCRIPT attribute of the tag. This prevents an applet from accessing JavaScript on a page without the knowledge of the page author. Attempting to access JavaScript from an applet that does not have the MAYSCRIPT attribute generates an exception. The MAYSCRIPT tag is needed only for Java to access JavaScript; it is not needed for JavaScript to access Java.

more...

LiveConnect 으로 해본 것은 모든 인터페이스를 스크립트로 구여하여 만든 소켓 사용 채팅이 있었다.
이 방법은 javascript의 많은 부분의 제약을 어느정도 효과적으로 활용 할 수 있는 방법이라 생각되어 진다.

Codepage & CharSet

드레 — Wed, 09 Mar 2005 13:33:49 GMT

HTML 이나 ASP 를 서비스할때 언어로 인한 문제에 대해 간단히 적어본다.

CODEPAGE 나 CHARSET 을 바꿔주는 설정으로 언어설정으로 가능하다. 중국어 간체를 예로 보겠다.

첫번째 1 ASP

<%
Response.CharSet = "GB2312"
Session.CodePage = 936

Response.Write("返回部落")
Response.Write(", ")
Response.Write("返回上?")

// 깨지지 않는 이유는 UTF-8로 저장하였을시 화면에 뿌려줄때는 유니코드의 문자들이
// Response.CharSet으로 지정한 GB2312의 간체의 맞는 ANSI 로 변환해준다.

// 하지만 이 방법도 ANSI로 저장하였을 경우 마지막 글씨가 깨진다.
// ANSI -> GB2312 변환시 마지막 ?로 표시되는
// 글씨는 현재 설정된 언어 ANSI코드에 없는 문자이기 때문에 표시되지 않는다.
// 한자를 잘 복사해서 붙여 넣고 제대로 返回上级로 표시되는
// 상태에서 UTF-8로 저장을 하면 제대로 표시된다 권장한다.

%>

두번째 경우 2 HTML

返回部落, 返回上?

Cache Misses and Page Faults

드레 — Fri, 07 Jan 2005 07:21:49 GMT

MSDN : ms-help://MS.MSDNQTR.2003FEB.1033/vccore/html/_core_Tips_for_Improving_Time.2d.Critical_Code.htm

Cache Misses and Page Faults
Missed cache hits, on both the internal and external cache, as well as page faults (going to secondary storage for program instructions and data) slow the performance of a program.

A CPU cache hit can cost your program 10-20 clock cycles. An external cache hit can cost 20-40 clock cycles. A page fault can cost one million clock cycles (assuming a processor that handles 500 million instructions/second and a time of 2 millisecond for a page fault). Therefore, it is in the best interest of program execution to write code that will reduce the number of missed cache hits and page faults.

One reason for slow programs is that they take more page faults or miss the cache more often than necessary. To avoid this, it's important to use data structures with good locality of reference, which means keeping related things together. Sometimes a data structure that looks great turns out to be horrible because of poor locality of reference, and sometimes the reverse is true. Here are two examples:

Dynamically allocated linked lists can reduce program performance because when you search for an item or when you traverse a list to the end, each skipped link could miss the cache or cause a page fault. A list implementation based on simple arrays might actually be much faster because of better caching and fewer page faults even - allowing for the fact that the array would be harder to grow, it still might be faster.

Hash tables that use dynamically allocated linked lists can degrade performance. By extension, hash tables that use dynamically allocated linked lists to store their contents might perform substantially worse. In fact, in the final analysis, a simple linear search through an array might actually be faster (depending on the circumstances). Array-based hash tables (so-called "closed hashing") is an often-overlooked implementation which frequently has superior performance

캐쉬 실패율과 페이지 실패율에 신경이 쓰이는 이유이다.

Sphere tree

드레 — Wed, 29 Dec 2004 03:58:00 GMT

sphere tree (구면 트리)

구면 트리는 객체들을 구면들의 계통 구조로 조직화 한다.

모든 자식 구면들을 담는 하나의 루트 노드가 존재한다.

자식들은 적절한 크기의 경계구들이 트리를 채울 때까지 재귀적으로 점차 분할된다.

객체가 한 구면 안에서 움직이다가 부모의 경계를 벗어나면 벗어난 위치를 담을 수 있을 정도로 부모를 키운다.

(담을수 있을 정도로 키운다. 분할이 아닌것으로 알고 있다.)

어떠한 최대 크기에 도달했다면, 객체를 그 부모의 부모 구면으로 올려 보내고 새로운 자식 구면을 만들어서 집어넣는다.

Cell 거리 기반 알고리즘에서 Oct Tree를 써보았다.

Oct Tree를 생각해 볼 때 각 Cell은 Oct-Tree에서 하나의 노드이며.

Cell 9개가 관심 반경, 또한 이것이 한개의 부모 Cell이라고 생각했을시 9개의 Cell이 모이면 또 하나의 부모 Cell 에 포함되는 개념이였다.

Game Programming Gems 2 권에서는 구면 트리의 알고리즘과 예제 소스를 제공 했다. Game Programming Gems 3 권에서는 서버에서의 구현 방향을 설명 하고 있다.

책에 의하면 다른 자료 구조 보다 조건 판단은 많이 일어 나지만 CPU를 거의 쓰지 않도록 구안해낸 자료구조이며, 객체들의 빈번한 삽입 삭제 또한 부담이 없다고 나와 있다. 이 부분이 구면트리에 흥미를 갖게했던 대목이였다.

일년전쯤 구면트리로 구현해보기 위해 고심했던 기억이 떠오른다. 그때는 접었었다고 해야 하나 관심이 식었다고 해야 하나..

다시 한번 심리스와 구면트리에 관심을 갖어보려 한다.

- 드레 -

삼선 슬리퍼...

드레 — Tue, 28 Dec 2004 03:32:26 GMT

명칭은 삼선 슬리퍼라고 불리운다 한다. 사실 아디다스 슬리퍼의 모조품이라는게 더 정확할 것 같다.

눈씻고 사무실에 삼선 슬리퍼를 신고 다니는 분들을 찾아보았지만. 신기하게도 아무도 없었다.

불과 일년전만해도 사람에 사람을 거쳐 사무실 구석에 쳐박혀 있는 몇켤레 슬리퍼들 중에 한번쯤은 나에게도 거쳐간 슬리퍼였는데.

자주 보이던 하얀 세가닥의 선 모양이 기억속에서 점차 희미해 질 때
버스안 이 추운 겨울 맨발로 슬리퍼를 신고 하얀 세가닥의 추억을 다시 회상하게 해주며 달려내려가는 이가 있었으니...

그것은 교복차림에 자랑스러운 우리나라 고등학생이였다.. 꽤 추워보이던데... (ㅡ_ㅡ;)

프로그래밍을 처음 시작할 무렵 회사에 틀어박혀 몇날 몇일을 보내던 시절 칙칙한 사무적 물건들과 뒤섞여 떠오르는 삼선 슬리퍼...

왠지 답답한 사무실에 해가 저무는지 조차 모르며 열의를 허비했던 그때가 삼선 슬리퍼와 함께 칙칙한 기억으로 밖에 회상되지 않는 이유는 무엇일까...

그래서일것이다. 이상하게도 삼선 슬리퍼는 다른 이들에게도 백수 + 내츄럴이라는 용어가 따라붙기 시작함이 나에게도 공감이라는 단어로 와 닿는 이유는...

블로그 이후에는...

드레 — Sat, 25 Dec 2004 17:53:05 GMT

몇주전 구글을 통해 이 이글루스를 접하게 되었다. 블로그라는 자체에 관심이 가며 떠오른 생각이란...

과거 언제나 익명성이 문제시 되어오지 않았었나 인터넷이라는 공간은...

그 공간의 의외로 사람들의 흐름은 자신들의 이름으로 스스로를 드러내고 싶어 하고 있었다는 것이였나보다.

어떠한 한정적 인연으로 자신을 드러내보였던 싸이월드라면...

블로그라는 이름으로 좀더 쉽게 더 넓은 다수에게 스스로를 드러내기 시작하고 있다는 것인가...?

이러한 부분에서 싸이에 페이퍼라는 대처는 대단하다 생각할 수 밖에 없었을지도 모른다.

언제나 이러한 것들은 많은 다른 형태로 시도되어 왔었지만 아마 얼마나 누구나 쉽게 그러한 것에 접근할 수 있었는가가 관건이였던게 아닐까.

과연 이러한 것에 대한 상호연관성에 대한 끈이 어떠한 것이 되려는 건지... 검색... 페이퍼... 이러한 건가...

이제 앞으로는 어떠한 흐름일 것인지... 어디 유명한 쪽집게 점쟁이나 찾아가보까나...

한해가 저물며...

드레 — Thu, 23 Dec 2004 07:13:38 GMT

망년회라는 뜻은 그해의 온갖 괴로움을 잊는다는 뜻을 지녔기에 송년회라는 용어를 사용하라는 어디선가 흘러나오는 이야기를 열심히 귀에 쓸어 담은적이 있다.

잦아지는 송년회로 마땅히 모일만한 장소또한 찾기 힘든 일. 어찌됬든 그곳만은 피하고 싶다.

불.닭 (아마 갔던 곳이 어설픈 음식점이였던가? 이렇게 매운걸 먹어보긴 처음이다.)

아마 올 겨울 음식 트렌드는 불닭인가보다.
동네 먹자골목이 있기에 항시 순식간에 변해가는 음식 트렌드를 한눈에 볼수 있다.

괴롭게도 먹자골목에서 올 겨울은 불닭이랜다... (불경기의 여파인가...)

언제 우유 한통 들고 가서 다시한번 도전해보리이다...

사람에게 있는 6가지 감옥..

드레 — Thu, 23 Dec 2004 04:29:33 GMT

어떤 심리학자의 말에 의하면 사람에게는 6가지 감옥이 있다고 합니다.

첫째 감옥은 자기 도취의 감옥입니다.
공주병, 왕자병에 걸리면 정말 못 말립니다.

둘째 감옥은 비판의 감옥입니다.
항상 다른 사람의 단점만 보고 비판하기를 좋아합니다.

셋째 감옥은 절망의 감옥입니다.
항상 세상을 부정적으로만 보고 불평하며 절망합니다.

넷째 감옥은 과거 지향의 감옥입니다.
옛날이 좋았다고 하면서 현재를 낭비합니다.

다섯째 감옥은 선망의 감옥입니다.
내 떡의 소중함은 모르고 남의 떡만 크게 봅니다.

여섯째 감옥은 질투의 감옥입니다.
남이 잘 되는 것을 보면 괜히 배가 아프고 자꾸 헐뜯고 싶어집니다.

사람은 이 6가지 감옥에서 탈출하지 않으면 결코 행복할 수 없다고 말합니다.

- 출처 : 미친병아리가 삐약삐약 -