Monthly Archives: August 2013

Links related to Self-organising linked list.

The following are some links related to Self-organising linked list which I
will be studying in this week :

Self-organizing list – Wikipedia, the free encyclopedia
http://en.wikipedia.org/wiki/Self-organizing_list

courses.cs.vt.edu/~cs2604/spring04/Notes/C16.SelfOrganizingLists.pdf
http://courses.cs.vt.edu/~cs2604/spring04/Notes/C16.SelfOrganizingLists.pdf

www.eecs.yorku.ca/course_archive/2003-04/F/2011/2011A/DatStr_071_SOLists.pdf
http://www.eecs.yorku.ca/course_archive/2003-04/F/2011/2011A/DatStr_071_SOLists.pdf

CPS 100, Spring 1997, Self-Organizing Lists
http://www.cs.duke.edu/~ola/courses/cps100/spr97/group/selforglist.html

people.scs.carleton.ca/~oommen/papers/ValivetiOommenDLL93.pdf
http://people.scs.carleton.ca/~oommen/papers/ValivetiOommenDLL93.pdf

Dictionaries
https://www8.cs.umu.se/kurser/TDBA77/VT06/algorithms/BOOK/BOOK3/NODE129.HTM

[FileSystem][DSAOW] Week 35 – DS and Algo of the week & also mmap.

Data structure of the week : Self organising linked lists.
Algorithms of the week : Self organising linked lists.

I have been seeing a video lecture on filesystems and it has mentions to
mmap.
I had a very wrong idea of memory mapped files and it was corrected in the
lecture.
I have also checked these other excellent articles on mmap.
http://www.devshed.com/c/a/BrainDump/Using-mmap-for-Advanced-File-IO/
http://www.devshed.com/c/a/BrainDump/The-MMAP-System-Call-in-Linux/

How fast is a write to memory as compared to disk drives?

This is a very good representation of the speed of writes to RAM as against
the speed of the disk drive.
This test was carried on a 2.4 GHz 8-core i7, 8GB RAM Ubuntu laptop.

>>Writing to swap which will be basically memory mapped file
time dd if=/dev/zero of=/run/zero ibs=10240 count=10000
10000+0 records in
200000+0 records out
102400000 bytes (102 MB) copied, 0.161455 s, 634 MB/s
0.00 user
0.15 system
0:00.16 elapsed 97%CPU (0 avg text+ 0 avg data 3696 maxresident)k
0 inputs + 0 outputs ( 0 major + 285 minor ) pagefaults 0 swaps

>> Writing to file system
time dd if=/dev/zero of=/home/user/zero ibs=10240 count=10000
10000+0 records in
200000+0 records out
102400000 bytes (102 MB) copied, 0.394104 s, 260 MB/s

real 0m0.396s
user 0m0.012s
sys 0m0.380s

It would be very interesting to see what will be the results on an android
device, which has mostly flash storage.
There was the following link floating around HN some time back which listed
some of the latencies, pasting a short excerpt :

>>>>

L1 cache reference 0.5 ns
.
.
Main memory reference 100 ns 20x L2
cache, 200x L1 cache
.
.
Disk seek 10,000,000 ns 10 ms 20x
datacenter roundtrip
Read 1 MB sequentially from disk 20,000,000 ns 20 ms 80x
memory, 20X SSD
Send packet CA->Netherlands->CA 150,000,000 ns 150 ms

>>>>

The following link has all the complete list :
https://gist.github.com/jboner/2841832

Browser-docs: Chromium graphics documentation.

Chromium, the open source browser from Google has some a complex graphics
rendering system.
There is some vast documentation available on the sites, but some of the
documents are hosted on Google Docs, which is unfortunately not accessible
in our office.
Hence I have made pdfs of the same documents and hosted them here on
flaminghorns.com.
The document list can be accessed here :
http://flaminghorns.com/chromium_graphics/

Self-help books to be read for the month of August 2013

The following books will be read and notes for the same posted in the month
of August 2013:
1) Decisive: How to Make Better Choices in Life and Work – by Chip Heath,
Dan Heath
2) Made to Stick: Why Some Ideas Survive and Others Die – by Chip Heath,
Dan Heath
3) How to Live on 24 Hours a Day – by Arnold Bennett
4) Mental Efficiency – by Arnold Bennett

I have already completed #3. I may post notes which others have already
posted. No point in redocumenting some stuff.
Also one coding exercise for the month needs to be decided. This could be
any coding problem which I could solve using my programming expertise. Let
me see where I can get good problems to code for.

Reading list for August 2013.

From this month on, I will be posting the list of books & articles which
will be read in that month.
Basically the reading list will be published and the notes for those
books/articles will be posted as well.
This month I am checking out self-help books & books on file system.
File System related books and articles
1. Persistence from Operating Systems: Three Easy Pieces :
http://pages.cs.wisc.edu/~remzi/OSTEP/
2. Practical File system Design –
http://www.nobius.org/~dbg/practical-file-system-design.pdf
3. The Design and Implementation of a Log-Structured File System –
http://www.cs.berkeley.edu/~brewer/cs262/LFS.pdf

Self-help books
[[
Need to figure out which ones to read, lots of them on offer, but very few
are the good ones.
]]

After a month I am going to update my effort into developing a reading
habit with this monthly reading list.