What is the difference between department and faculty? Some universities have independent departments, but some put departments under supervision of a faculty. For instance, a university has fifty independent departments, but another has 5 faculties containing departments. In the former, the Dean of Faculty is intermediate between the department chairs and the university administration.

I understand that most of these structures come from the university history, but how these structures affect the department performance, and why universities prefer different structures, instead of a standard one (which should be most efficient).

For example, what is the different of Department of Computer Science in one university, and Department of Computer Science in another university which is part of Faculty of Engineering?
The distinction between "faculty," "department," and "school" depends a lot on where you are. As Peter suggests in his answer, a faculty can be a collection of "departments." However, a faculty in Germany (for instance) consists of a number of "chairs," each of which is closer to a professorship in a department than an actual "department." Thus, the faculty is effectively halfway between the American "department" and "faculty" in its function, as it combines some of the hierarchy and responsibilities of each.

The reason for having multiple subdivisions is that there are often many university functions—including personnel and budget decisions, facilities management, teaching, and so on—that can vary widely across the entire university, but significantly less among certain departments that have a similar focus. For these departments, it makes sense to combine these duties in a central administration, rather than duplicate the effort across multiple departments.